Problem: Write a program which manipulates a disjoint set S = {S1, S2, . . . , Sk}.

First of all, the program should read an integer n, then make a disjoint set where each element consists of 0, 1, ... n−1 respectively.

Next, the program should read an integer q and manipulate the set for q queries. There are two kinds of queries for different operations:

* unite(x, y): unites sets that contain x and y, say Sx and Sy, into a new set.
* same(x, y): determine whether x and y are in the same set.

Constraints

* 1 ≤ n ≤ 10000
* 1 ≤ q ≤ 100000
* x ≠ y

Input


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


In the first line, n and q are given. Then, q queries are given where com represents the type of queries. '0' denotes unite and '1' denotes same operation.

Output

For each same operation, print 1 if x and y are in the same set, otherwise 0, in a line.

Example

Input

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


Output

0
0
1
1
1
0
1
1

Solution (in JAVA):

Solution:
import java.io.*;

class Main{

static final PrintWriter out=new PrintWriter(System.out);

public static class UnionFindTree{

private static int[] par;
private static int[] rank;

public UnionFindTree(int size){
par=new int[size];
rank=new int[size];
for(int i=0;i<size;i++){
par[i]=i;
rank[i]=0;
}
}

private static int find(int x){
if(par[x]==x) return x;
else return par[x]=find(par[x]);
}

public static void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
else if(rank[x]>rank[y]) par[y]=x;
else{
par[x]=y;
if(rank[x]==rank[y]) rank[y]++;
}
}

public static boolean same(int x,int y){
return find(x)==find(y);
}
}

public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line="";
int num=Integer.parseInt(br.readLine().split(" ")[0]);
UnionFindTree tree=new UnionFindTree(num);
while((line=br.readLine())!=null&&!line.isEmpty()){
String[] values=line.split(" ");
int query=Integer.parseInt(values[0]);
int x=Integer.parseInt(values[1]);
int y=Integer.parseInt(values[2]);
if(query==0) tree.unite(x,y);
else out.println(tree.same(x,y)?"1":"0");
}
out.flush();
}
}