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 PYTHON3):

Solution:
import sys
sys.setrecursionlimit(10000)


class Node:
    
    def __init__(self):
        self.root = self
        self.child = None
        self.length = 1
    
    def set_root(self, root):
        if self.child:
            self.child.set_root(root)
        self.root = root
            
    def set_child(self, child):
        if self.child:
            self.child.set_child(child)
        else:
            self.child = child
        
        
n,q = [int(i) for i in input().split()]
A = []
for i in range(n):
    A.append(Node())

for i in range(q):
    c, x, y = [int(i) for i in input().split()]
    if c == 0:
        if A[x].root == A[y].root:
            continue
        if A[x].root.length < A[y].root.length:
            A[y].set_child(A[x].root)
            A[y].root.length += A[x].root.length
            A[x].root.set_root(A[y].root)
        else:
            A[x].set_child(A[y].root)
            A[x].root.length += A[y].root.length
            A[y].root.set_root(A[x].root)
    else:
        if A[x].root == A[y].root:
            print(1)
        else:
            print(0)