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.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		DjSet djs = new DjSet(n);

		int q = scan.nextInt();
		for (int i = 0; i < q; i++)
			switch (scan.nextInt()) {
			case (0):
				djs.union(scan.nextInt(), scan.nextInt());
				break;
			case (1):
				if (djs.isSame(scan.nextInt(), scan.nextInt()))
					System.out.println("1");
				else
					System.out.println("0");
			}

		scan.close();
		System.exit(0);
	}
}

class DjSet {
	int[] parent;
	int[] height;

	public DjSet(int n) {
		parent = new int[n];
		height = new int[n];
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	public boolean isSame(int s1, int s2) {
		if (findSet(s1) == findSet(s2))
			return true;
		else
			return false;
	}

	public void union(int u1, int u2) {
		int p1 = findSet(u1);
		int p2 = findSet(u2);
		if (p1 == p2)
			return;
		if (height[p1] > height[p2])
			parent[p2] = p1;
		else if (height[p1] == height[p2]) {
			height[p1]++;
			parent[p2] = p1;
		} else
			parent[p1] = p2;
	}

	private int findSet(int id) {
		if (parent[id] != id)
			parent[id] = findSet(parent[id]);
		return parent[id];
	}
}