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à hai đỉ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.

Constraints

• \(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\).

Example

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

10