Cutting a graph

Xem dạng PDF

Gửi bài giải

Điểm: 0,01 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.