영속 유니온 파인드

$G_{-1}$을 $N$개의 정점과 간선이 없는 그래프라 하자. $Q$개의 쿼리를 순서대로 처리한다. $i$번째 쿼리는 다음 형식으로 주어진다.

• 0 $k_{i}$ $u_{i}$ $v_{i}$: $G\_{k\_{i}}$에 간선 $\left( u, v \right)$을 추가하여 만든 그래프를 $G\_{i}$라 하자.
• 1 $k_{i}$ $u_{i}$ $v_{i}$: $G\_{k\_{i}}$에서 정점 $u, v$가 연결되어 있으면 $1$을 출력한다. 그렇지 않으면 $0$을 출력한다.

제한

• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $t\_{i} \in \left\lbrace 0, 1 \right\rbrace$
• $-1 \leq k\_{i} < i$
• 모든 $k_i$에 대해, $k\_i = -1$ 또는 $t\_{k\_{i}} = 0$가 성립한다.
• $0 \leq u\_{i}, v\_{i} < N$

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

1 $k_{i}$ $u_{i}$ $v_{i}$: $G\_{k\_{i}}$에서 정점 $u, v$가 연결되어 있으면 $1$을 출력한다. 그렇지 않으면 $0$을 출력한다.