Cho đồ thị vô hướng ~N~ đỉnh. Cho ~Q~ truy vấn, mỗi truy vấn thuộc ~1~ trong ~3~ loại:

1. Thêm cạnh ~(x~, ~y)~.
2. Xóa cạnh ~(x~, ~y)~.
3. Kiểm tra xem ~2~ đỉnh ~x~, ~y~ có liên thông với nhau không.

Input

• Dòng đầu tiên chứa ~2~ số ~N~, ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn có dạng: ~t~ ~x~ y. Trong đó ~t = 1~, ~2~ hoặc ~3~ tương ứng với truy vấn ~1~, ~2~ hoặc ~3~; ~x~, ~y~ là ~2~ đỉnh trên đồ thị ~(1 \le x~, ~y \le N)~.

Output

• Với mỗi truy vấn loại ~3~, in ra ~1~ nếu ~2~ đỉnh ~x~, ~y~ liên thông, ~0~ trong trường hợp ngược lại.
• Các số được in liên tiếp nhau trên cùng một dòng.

Giới hạn

• ~2 \le N \le 10^{5}~
• ~1 \le Q \le 10^{5}~
• Trong cùng một thời điểm, có thể có nhiều cạnh giữa ~2~ đỉnh ~x~, ~y~ (đa đồ thị).
• Đối với truy vấn loại ~2~: nếu có nhiều cạnh ~(x~, ~y)~, xóa ~1~ cạnh bất kì; nếu không có cạnh nào, không làm gì cả.
• Trong ~50\%~ tổng số test, ~1 \le N~, ~Q \le 5000~.

Sample Input

2 4
1 1 2
3 2 1
2 2 1
3 1 2

Sample Output

10