8820: [yosupo] Data Structure - Unionfind
[Creator : ]
Description
We have an undirected graph with $N$ vertices and $0$ edges.
Process the following $Q$ queries in order:
- $t_i$ = 0 $u_i$ $v_i$: Add an edge $(u, v)$.
- $t_i$ = 1 $u_i$ $v_i$: If vertices $u, v$ are connected, print $1$. Otherwise, print $0$.
Process the following $Q$ queries in order:
- $t_i$ = 0 $u_i$ $v_i$: Add an edge $(u, v)$.
- $t_i$ = 1 $u_i$ $v_i$: If vertices $u, v$ are connected, print $1$. Otherwise, print $0$.
Input
$N$ $Q$
$t_1$ $u_1$ $v_1$
$t_2$ $u_2$ $v_2$
:
$t_Q$ $u_Q$ $v_Q$
$t_1$ $u_1$ $v_1$
$t_2$ $u_2$ $v_2$
:
$t_Q$ $u_Q$ $v_Q$
Constraints
$1 \leq N \leq 200,000$
$1 \leq Q \leq 200,000$
$0 \leq u_i, v_i \lt N$
$1 \leq Q \leq 200,000$
$0 \leq u_i, v_i \lt N$
Sample 1 Input
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3
Sample 1 Output
0
1
0
1