Cho một đồ thị vô hướng và một dãy các truy vấn thuộc một trong hai loại sau:
cut ~u~ ~v~ — xóa cạnh ~u-v~ khỏi đồ thị;
ask ~u~ ~v~ — kiểm tra xem hai đỉnh ~u~ và ~v~ có cùng thuộc một thành phần liên thông hay không.
Sau khi thực hiện tất cả truy vấn, đồ thị không còn cạnh nào. Tìm đáp án cho mỗi truy vấn thuộc loại ask.
Input
Dòng đầu tiên gồm ba số nguyên dương ~n, m~ và ~k~ (~1 \le n \le 50000, 0 \le m \le 100000, m \le k \le 150000~) — lần lượt là số lượng đỉnh, số lượng cạnh trong đồ thị và số lượng truy vấn cần thực hiện.
Mỗi dòng trong ~m~ dòng tiếp theo gồm hai số nguyên dương ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~) — hai đỉnh của cạnh thứ ~i~. Các đỉnh được đánh số từ ~1~, đồ thị không có khuyên và cạnh lặp.
Mỗi dòng trong ~k~ dòng tiếp theo mô tả một trong hai loại truy vấn sau:
"cut ~u~ ~v~" — xóa cạnh giữa đỉnh ~u~ và ~v~
"ask ~u~ ~v~" — kiểm tra xem hai đỉnh ~u~ và ~v~ có cùng thuộc một thành phần liên thông hay không
Mỗi cạnh trong đồ thị xuất hiện trong các truy vấn cut một lần.
Output
Với mỗi truy vấn thuộc loại ask, in ra "YES" nếu hai đỉnh đã cho cùng thuộc một thành phần liên thông, và "NO" trong trường hợp còn lại. Thứ tự in ra đáp án tương đương với thứ tự truy vấn ask xuất hiện.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~30~ | ~1 \le n, k \le 10^3~ |
2 | ~70~ | Không có ràng buộc gì thêm |
Sample Input 1
3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1
Sample Output 1
YES
YES
NO
NO
Bình luận