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.InputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
     
public class Main{
    
    static InputReader ir;
    static PrintWriter out;

    static void solve(){
        UnionFindTree tree=new UnionFindTree(ir.nextInt());
	int q=ir.nextInt();
	while(q-->0){
	    int query=ir.nextInt();
	    int x=ir.nextInt();
	    int y=ir.nextInt();
	    if(query==0) tree.unite(x,y);
	    else out.println(tree.same(x,y)?"1":"0");
	}
    }
    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 Exception {
	ir = new InputReader(System.in);
     	out = new PrintWriter(System.out);
	solve();
	out.flush();
     }
 
    static class InputReader {
	private InputStream in;
	private byte[] buffer=new byte[1024];
	private int curbuf;
	private int lenbuf;

	public InputReader(InputStream in) {this.in=in; this.curbuf=this.lenbuf=0;}
   
	public boolean hasNextByte() {
	    if(curbuf>=lenbuf){
		curbuf= 0;
		try{
		    lenbuf=in.read(buffer);
		}catch(IOException e) {
		    throw new InputMismatchException();
		}
		if(lenbuf<=0) return false;
	    }
	    return true;
	}
  
	private int readByte(){if(hasNextByte()) return buffer[curbuf++]; else return -1;}
 
	private boolean isSpaceChar(int c){return !(c>=33&&c<=126);}
  
	private void skip(){while(hasNextByte()&&isSpaceChar(buffer[curbuf])) curbuf++;}
 
	public boolean hasNext(){skip(); return hasNextByte();}
  
	public String next(){
	    if(!hasNext()) throw new NoSuchElementException();
	    StringBuilder sb=new StringBuilder();
	    int b=readByte();
	    while(!isSpaceChar(b)){
		sb.appendCodePoint(b);
		b=readByte();
	    }
	    return sb.toString();
	}
  
	public int nextInt() {
	    if(!hasNext()) throw new NoSuchElementException();
	    int c=readByte();
	    while (isSpaceChar(c)) c=readByte();
	    boolean minus=false;
	    if (c=='-') {
		minus=true;
		c=readByte();
	    }
	    int res=0;
	    do{
		if(c<'0'||c>'9') throw new InputMismatchException();
		res=res*10+c-'0';
		c=readByte();
	    }while(!isSpaceChar(c));
	    return (minus)?-res:res;
	}
  
	public long nextLong() {
	    if(!hasNext()) throw new NoSuchElementException();
	    int c=readByte();
	    while (isSpaceChar(c)) c=readByte();
	    boolean minus=false;
	    if (c=='-') {
		minus=true;
		c=readByte();
	    }
	    long res = 0;
	    do{
		if(c<'0'||c>'9') throw new InputMismatchException();
		res=res*10+c-'0';
		c=readByte();
	    }while(!isSpaceChar(c));
	    return (minus)?-res:res;
	}
  
	public double nextDouble(){return Double.parseDouble(next());}
  
	public int[] nextIntArray(int n){
	    int[] a=new int[n];
	    for(int i=0;i<n;i++)
		a[i]=nextInt();
	    return a;
	}
  
	public char[][] nextCharMap(int n,int m){
	    char[][] map=new char[n][m];
	    for(int i=0;i<n;i++)
		map[i]=next().toCharArray();
	    return map;
	}
    }
}