Truy vấn kết nối có hoàn tác

Cho một đồ thị vô hướng có $N$ đỉnh, ban đầu không có cạnh nào. Đỉnh được đánh số từ $1$ đến $N$.

Bạn cần xử lý $M$ thao tác, mỗi thao tác có một trong ba dạng sau:

• + u v — Thêm một cạnh nối hai đỉnh $u$ và $v$. Cho phép có nhiều cạnh trùng nhau giữa cùng một cặp đỉnh (multi-edge).
• - u v — Xoá một cạnh nối $u$ và $v$. Dữ liệu đảm bảo rằng tại thời điểm thao tác này, có ít nhất một cạnh $(u,v)$ đang tồn tại. Nếu có nhiều cạnh trùng nhau giữa $u$ và $v$, chỉ một trong số đó bị xoá.
• ? u v — Truy vấn: hãy in YES nếu $u$ và $v$ đang nằm trong cùng một thành phần liên thông sau tất cả các thao tác đã thực hiện trước đó, ngược lại in NO.

Lưu ý: cạnh là vô hướng, và một đỉnh luôn liên thông với chính nó (truy vấn dạng ? u u luôn trả lời YES).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo, mỗi dòng là một trong ba thao tác được mô tả ở trên: một ký tự (+, - hoặc ?) theo sau là hai số nguyên $u$, $v$.

Dữ liệu ra

Với mỗi thao tác ?, in một dòng chứa YES hoặc NO theo thứ tự xuất hiện của truy vấn.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le M\le 2·{10}^5$
• $1\le u,v\le N$
• Với mọi thao tác - u v, đảm bảo có ít nhất một cạnh $(u,v)$ đang tồn tại tại thời điểm đó.

Ví dụ

Ghi chú

Bài toán yêu cầu xử lý cả phép thêm và phép xoá cạnh. Cấu trúc Union-Find thông thường không hỗ trợ xoá hiệu quả. Hãy nghĩ cách xử lý offline: đọc trước toàn bộ thao tác, sau đó xử lý chúng theo một thứ tự khéo léo hơn.