Nhóm nghiên cứu lý thuyết đồ thị tại FPTU cần kiểm tra tính hai phía (bipartite) của một đồ thị đang thay đổi liên tục.

Một đồ thị gọi là hai phía nếu có thể tô màu tất cả đỉnh bằng hai màu sao cho không có cạnh nào nối hai đỉnh cùng màu. Tương đương, đồ thị là hai phía khi và chỉ khi không chứa chu trình độ dài lẻ.

Đồ thị \(N\) đỉnh, ban đầu không có cạnh. Hệ thống nhận \(Q\) thao tác:

• add u v — Thêm cạnh \((u, v)\) vào đồ thị (đảm bảo cạnh chưa tồn tại).
• remove u v — Xóa cạnh \((u, v)\) khỏi đồ thị (đảm bảo cạnh đang tồn tại).
• query — In YES nếu đồ thị hiện tại là hai phía, NO nếu không.

Lưu ý: Đồ thị không liên thông là hai phía khi và chỉ khi mọi thành phần liên thông đều là hai phía.

Gợi ý: Dùng DSU với thông tin tính chẵn lẻ (parity DSU) kết hợp D&C trên thời gian.

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác.

Định dạng đầu ra

Với mỗi thao tác query, in YES hoặc NO trên một dòng riêng.

Ví dụ

Input:

3 7
add 1 2
add 2 3
query
add 1 3
query
remove 1 3
query

Output:

YES
NO
YES

Giải thích:

• Cạnh {1–2, 2–3}: đường thẳng 1–2–3, tô màu xen kẽ được → hai phía → YES.
• Thêm 1–3: tạo tam giác {1,2,3} — chu trình độ dài 3 (lẻ) → không hai phía → NO.
• Xóa 1–3: quay về đường thẳng → hai phía → YES.

Ràng buộc

\(1 \le u, v \le N\), \(u \ne v\).