$N$個の頂点からなる根のない木の森 $F$ がある。最初、$F$ に属するすべての木は1つの頂点のみからなる木である。以下のようなクエリを実行する。

• 1 A B: 頂点 $A$ と $B$ を結ぶ辺を追加する。クエリが与えられる前に $A$ と $B$ の間には辺はない。
• 2 A B: 頂点 $A$ と $B$ を結ぶ辺を削除する。クエリが与えられる前に $A$ と $B$ の間には辺がある。
• 3 A B: 頂点 $A$ から $B$ への経路が存在するかどうかを調べる。存在する場合は $1$、存在しない場合は $0$ を出力する。

すべての $A$ と $B$ は $1 \le A, B \le N$, $A \ne B$ を満たし、すべての辺は無向である。

入力

1行目に頂点の個数 $N$ ($2 \le N \le 100{,}000$) とクエリの個数 $M$ ($1 \le M \le 100{,}000$) が与えられる。2行目から $M$ 行にクエリが1行に1つずつ与えられる。すべてのクエリの実行結果が森であるような入力のみが与えられる。

出力

3番目のクエリの結果を1行に1つずつ出力する。

入出力例

入力 1

5 11
3 1 5
1 1 2
1 1 3
1 3 4
1 5 4
3 1 5
2 4 5
3 1 5
2 3 4
1 3 5
3 1 5

出力 1

0
1
0
1