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.util.*;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = scanner.nextInt();
        int Q = scanner.nextInt();
        scanner.nextLine();

        WeightedUnionFindTree uft = new WeightedUnionFindTree(N);
        for (int i = 0; i < Q; i++) {
            int[] q = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if (q[0] == 0) {
                uft.merge(q[1], q[2]);
            } else {
                System.out.println(uft.same(q[1], q[2]) ? 1: 0);
            }
        }
    }

}

class WeightedUnionFindTree {
    int size;
    int[] par;
    int[] rank;
    int[] weight;

    public WeightedUnionFindTree(int size) {
        this.size = size;
        par = new int[size];
        for (int i = 0; i < size; i++) {
            par[i] = i;
        }
        rank = new int[size];
        Arrays.fill(rank, 1);
        weight= new int[size];
    }

    private int root(int x) {
        if (x == par[x]) {
            return x;
        }
        int root = root(par[x]);
        par[x] = root;
        // cSum
        weight[x] += weight[par[x]];
        return root;
    }

    private int weight(int x) {
        root(x);
        return weight[x];
    }

    public int diff(int x, int y) {
        return weight(y) - weight(x);
    }

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

    public void merge(int x, int y) {
        merge(x, y, 1);
    }

    public void merge(int x, int y, int w) {
        w += weight[x];
        w -= weight[y];

        int xr = root(x);
        int yr = root(y);

        if (xr == yr) {
            return;
        }

        if (rank[xr] < rank[yr]) {
            par[xr] = yr;
            weight[y] = -w;
        } else {
            par[yr] = xr;
            if (rank[xr] == rank[yr]) {
                rank[xr]++;
            }
            weight[x] = w;
        }
    }

}