# Persistent UnionFind

AC一覧

## Problem Statement問題文

Let $G_{-1}$ be the graph which consists of $N$ vertices and no edges. Process $Q$ queries in order. The $i$-th query is given with the following format:

• 0 $k_{i}$ $u_{i}$ $v_{i}$: Let $G_{i}$ be the graph, which is made by adding an edge $\left( u, v \right)$ to $G_{k_{i}}$.
• 1 $k_{i}$ $u_{i}$ $v_{i}$: If vertices $u, v$ in $G_{k_{i}}$ are connected, print $1$. Otherwise, print $0$.

$G_{-1}$ を、$N$ 個の頂点からなる、辺がひとつも存在しないグラフとします。$Q$ 個のクエリを処理してください。$i$ 個目のクエリは以下の形式で与えられます。

• 0 $k_{i}$ $u_{i}$ $v_{i}$: $G_{k_{i}}$ に辺 $\left( u_{i}, v_{i} \right)$ を追加したグラフを $G_{i}$ とする。
• 1 $k_{i}$ $u_{i}$ $v_{i}$: グラフ $G_{k_{i}}$ において $u_{i}, v_{i}$ が連結ならば $1$ を、そうでなければ $0$ を出力する。

## Constraints制約

• $1 \leq N \leq 200{,}000$
• $1 \leq Q \leq 200{,}000$
• $t_{i} \in \left\{ 0, 1 \right\}$
• $-1 \leq k_{i} < i$
• for all $k_i$, $k_i = -1$ or $t_{k_{i}} = 0$ holds.
• $0 \leq u_{i}, v_{i} < N$

## Input入力

$N$ $Q$
$t_0$ $k_0$ $u_0$ $v_0$
$\vdots$
$t_{Q-1}$ $k_{Q-1}$ $u_{Q-1}$ $v_{Q-1}$


## Sampleサンプル

### # 1

5 12
0 -1 0 1
0 0 0 2
1 -1 0 1
1 0 0 1
1 1 0 1
0 1 3 4
0 1 2 3
1 5 1 4
0 5 2 3
1 8 1 4
0 6 3 4
1 10 1 4

0
1
1
0
1
1


Timelimit: 5 secs

Before submitting, please confirm terms and conditions