Giải bài trực tuyến

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.

Giới hạn:

• 2 <= N <= 10^5
• 1 <= Q <= 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 <= N, Q <= 5000.

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 <= x, y <= 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.

Ví dụ: