Cho một đồ thị vô hướng gồm \(N\) đỉnh và \(0\) cạnh. Bạn hãy xử lý \(Q\) truy vấn sau:

• 0 u v: Thêm một cạnh \((u, v)\) vào đồ thị.
• 1 u v: Kiểm tra xem \(u\) và \(v\) có cùng thuộc một thành phần liên thông hay không.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) \(\left(1\leq N, Q\leq 2\times 10^5\right)\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn có dạng 0 u v hoặc 1 u v. Dữ liệu đảm bảo \(0\leq u, v < N\).

Output

• Với mỗi truy vấn dạng 1 u v, in ra \(1\) nếu \(u\) và \(v\) cùng nằm trong một thành phần liên thông, và in ra \(0\) trong trường hợp ngược lại.

Ví dụ

Sample input 01

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

Sample output 01

0
1
0
1