互いに素な集合

互いに素な動的集合 S = {S₁, S₂,...,S_k} を管理するプログラムを作成してください。

まず、整数 n を読み込み、0, 1, ... n-1 をそれぞれ唯一の要素とする n 個の互いに素な集合を作成します。

次に、整数q を読み込み、q 個のクエリに応じて集合を操作します。クエリは以下の2種類を含みます：

• unite(x, y): x を含む集合 S_x と y を含む集合 S_y を合併する。
• same(x, y): x と y が同じ集合に属しているかを判定する。

入力

n q
com1 x1 y1
com2 x2 y2
...
comq xq yq

１行目に n, q が与えられます。続く q 行にクエリが与えられます。com_i は、クエリの種類を示し、'0' が unite、'1' が same を表します。

出力

各 same クエリについて、x と y が同じ集合に属する場合 1 を、そうでない場合 0 を一行に出力してください。

制約

• 1 ≤ n ≤ 10,000
• 1 ≤ q ≤ 100,000
• x ≠ y

入力例

5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0

出力例

0
0
1
1
1
0
1
1

---