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:
//Do what you can't.
//use/application of Disjoint Set
 
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main {
  public static void main(String[] args) {
    InputReader in = new InputReader(System.in);
    PrintWriter w = new PrintWriter(System.out);
    int n = in.nextInt(), q = in.nextInt();
    DJSet ds = new DJSet(n);
    while (q-- > 0) {
      switch (in.nextInt()) {
      case 0: ds.union(in.nextInt(), in.nextInt() );
        break;
      case 1: w.println(ds.equiv(in.nextInt() , in.nextInt() ) ? 1 : 0);
        break;
      }
    }
    w.close();
  }
  public static class DJSet {
    public int[] upper;
 
    public DJSet(int n) {
      upper = new int[n];
      Arrays.fill(upper, -1);
    }
 
    public int root(int x) {
      return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
    }
 
    public boolean equiv(int x, int y) {
      return root(x) == root(y);
    }
 
    public boolean union(int x, int y) {
      x = root(x);
      y = root(y);
      if (x != y) {
        if (upper[y] < upper[x]) {
          int d = x;
          x = y;
          y = d;
        }
        upper[x] += upper[y];
        upper[y] = x;
      }
      return x == y;
    }
 
    public int countCompo() {
      int ct = 0;
      for (int u : upper)
        if (u < 0)
          ct++;
      return ct;
    }
  }
  static class InputReader {
 
    private final InputStream stream;
    private final byte[] buf = new byte[8192];
    private int curChar, snumChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream) {
      this.stream = stream;
    }
 
    public int snext() {
      if (snumChars == -1)
        throw new InputMismatchException();
      if (curChar >= snumChars) {
        curChar = 0;
        try {
          snumChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (snumChars <= 0)
          return -1;
      }
      return buf[curChar++];
    }
 
    public int nextInt() {
      int c = snext();
      while (isSpaceChar(c)) {
        c = snext();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = snext();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9')
          throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = snext();
      } while (!isSpaceChar(c));
      return res * sgn;
    }
 
    public long nextLong() {
      int c = snext();
      while (isSpaceChar(c)) {
        c = snext();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = snext();
      }
      long res = 0;
      do {
        if (c < '0' || c > '9')
          throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = snext();
      } while (!isSpaceChar(c));
      return res * sgn;
    }
 
    public int[] nextIntArray(int n) {
      int a[] = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = nextInt();
      }
      return a;
    }
 
    public String readString() {
      int c = snext();
      while (isSpaceChar(c)) {
        c = snext();
      }
      StringBuilder res = new StringBuilder();
      do {
        res.appendCodePoint(c);
        c = snext();
      } while (!isSpaceChar(c));
      return res.toString();
    }
 
    public String nextLine() {
      int c = snext();
      while (isSpaceChar(c))
        c = snext();
      StringBuilder res = new StringBuilder();
      do {
        res.appendCodePoint(c);
        c = snext();
      } while (!isEndOfLine(c));
      return res.toString();
    }
 
    public boolean isSpaceChar(int c) {
      if (filter != null)
        return filter.isSpaceChar(c);
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    private boolean isEndOfLine(int c) {
      return c == '\n' || c == '\r' || c == -1;
    }
 
    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);
    }
  }
}