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.

Constraints

* 1 \leq N \leq 200,000
* 1 \leq Q \leq 200,000
* 0 \leq u_i, v_i \lt N

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
:
t_Q u_Q v_Q


出力

For each query of the latter type, print the answer.

Example

Input

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


Output

0
1
0
1
import java.util.*;

class UF{
	public int[] a;
	public UF(int size){
		Arrays.fill(a=new int[size],-1);
	}
	public int root(int t){
		return a[t]<0?t:(a[t]=root(a[t]));
	}
	public boolean connect(int r,int s){
		r=root(r);
		s=root(s);
		if(r==s)
			return false;
		if(a[r]>a[s]){
			a[s]+=a[r];
			a[r]=s;
		}else{
			a[r]+=a[s];
			a[s]=r;
		}
		return true;
	}
	public boolean isConnected(int a,int b){
		return root(a)==root(b);
	}
	public int groupSize(int t){
		return -a[root(t)];
	}
}

public class Main{
	public static void main(String[] $){
		var s=new Scanner(System.in);

		var n=Integer.parseInt(s.next());
		var q=Integer.parseInt(s.next());

		var uf=new UF(n);

		for(int i=0;i<q;++i){
			var t=Integer.parseInt(s.next());
			var u=Integer.parseInt(s.next());
			var v=Integer.parseInt(s.next());

			if(t==0)
				uf.connect(u,v);
			else
				System.out.println(uf.isConnected(u,v)?1:0);
		}
	}
}
