5347: AtCoder Library Practice Contest —— A - Disjoint Set Union
[Creator : ]
Description
You are given an undirected graph with $N$ vertices and $0$ edges. Process $Q$ queries of the following types.
- $0\ u\ v$: Add an edge $(u,v)$.
- $1\ u\ v$: Print $1$ if $u$ and $v$ are in the same connected component, $0$ otherwise.
Input
Input is given from Standard Input in the following format:
$N\ Q$
$t_1\ u_1\ v_1$
$t_2\ u_2\ v_2$
$\vdots$
$t_Q\ u_Q\ v_Q$
$N\ Q$
$t_1\ u_1\ v_1$
$t_2\ u_2\ v_2$
$\vdots$
$t_Q\ u_Q\ v_Q$
Output
For each query of the latter type, print the answer.
Constraints
$1≤N≤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