Set - Disjoint Set: Union Find Tree

時間制限 : 3 sec, メモリ制限 : 131072 KB
英語版はこちら

互いに素な集合

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

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

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

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

入力

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

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

出力

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

制約

  • 1 ≤ n ≤ 10,000
  • 1 ≤ q ≤ 100,000
  • xy

入力例

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

Note

      解説