Trong một vương quốc có N người, mỗi người là bạn hoặc thù. Quy tắc: bạn của bạn là bạn, thù của thù là bạn. Có Q sự kiện:

• 1 u v: u và v là bạn.
• 2 u v: u và v là thù.
• 3 u v: hỏi quan hệ — in 1 nếu bạn, 2 nếu thù, 0 nếu chưa xác định.

Đầu vào

• Dòng đầu N (1 ≤ N ≤ \(10^5\)), Q (1 ≤ Q ≤ \(10^5\)).
• Q dòng tiếp theo, mỗi dòng mô tả sự kiện.

Đầu ra

Với mỗi sự kiện loại 3, in kết quả.

Ví dụ

Input:
5 6
1 1 2
2 2 3
1 3 4
3 1 3
3 1 4
3 2 5

Output:
2
1
0

Ràng buộc & Subtasks