Description

给定一个有 $N$ 个顶点和 $0$ 条边的无向图。处理以下类型的 $Q$个操作。

• 0 u v : 添加一条边 $(u,v)$
• 1 u v : 如果 $u$ 和 $v$ 在同一个连通分量中，打印 $1$， 否则打印 $0$.

Format

Input

第一行输入两个正整数 $N,Q(1 \leq N, Q \leq 2 \times 10^5)$

接下来 $Q$， 每行三个正整数 $t,u,v( t \in \{0,1\}, 1 \leq u, v \leq n)$表示对应的操作。

Output

对于后一种类型的每个查询，打印答案。

Samples

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

0
1
0
1