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

Ngoài lề một tí

Nếu bạn là thí sinh thi VNOI OIO '09, đọc đến đây chắc hẳn bạn đang mừng lắm. Bởi vì mãi mới tìm thấy bài đồ thị “tủ” để kiếm điểm. Chắc chắn bạn sẽ càng mừng hơn nếu như tôi nói với bạn rằng bài mà bạn chuẩn bị đọc ở đây không yêu cầu thuật toán đồ thị nào cả mà chỉ hỏi về phần mà ai cũng biết đó là biểu diễn đồ thị.

Đề bài

Chú ý: đồ thị trong bài này là đồ thị có hướng.

Bạn cần viết chương trình xử lý các yêu cầu sau:

• NEW n k, với k=0 hoặc k=1 (khởi tạo 1 đồ thị mới với n đỉnh, nếu k = 0 thì là đồ thị rỗng, nếu k = 1 thì là đồ thị đầy đủ, đồ thị đầy đủ này bao gồm n² cạnh, nghĩa là bao gồm cả các vòng u → u với 1 ≤ u ≤ n).
• ADD u v (thêm cạnh từ u → v nếu chưa có).
• DEL u v (xóa cạnh từ u → v nếu có).
• ANY (xóa một cạnh bất kì trong đồ thị nếu có).
• EDG u v (kiểm tra xem có cạnh từ u → v hay không).

Bạn hãy lập trình xử lý bài toán sau đây:

• Nhập vào M yêu cầu, hãy thực hiện lần lượt từng yêu cầu.
• Đối với những yêu cầu ANY, in ra cạnh bị xóa. Nếu không có cạnh nào thì in ra -1.
• Đối với những yêu cầu EDG u v, in ra YES/NO tương ứng với có hay không có cạnh từ u → v.

Dữ liệu

• Gồm nhiều dòng, mỗi dòng ghi một yêu cầu cần xử lý. Dòng cuối cùng ghi "END" báo hiệu kết thúc dữ liệu. Số yêu cầu cần xử lý không quá 10⁶.

Với yêu cầu dạng NEW, ta luôn có 1 ≤ n ≤ 1000. Dữ liệu đảm bảo yêu cầu đầu tiên luôn là yêu cầu dạng NEW và với các yêu cầu ADD, DEL, EDG, 1 ≤ u, v ≤ n.

Kết quả

Tương ứng với mỗi yêu cầu dạng ANY hay EDG là một dòng ghi kết quả.

• Đối với yêu cầu dạng ANY, ghi ra hai số u, v cho biết bạn muốn xóa cạnh u → v.
• Đối với yêu cầu dạng EDG, ghi ra "YES" hoặc "NO" tương ứng với việc đồ thị còn cạnh u → v hay không.

Ví dụ

Dữ liệu
NEW 4 0
ADD 1 2
ADD 2 3
ANY
EDG 1 2
END

Với dữ liệu mẫu trên đây, hai kết quả mẫu sau đây đều hợp lệ:
Kết quả
2 3
YES

Kết quả
1 2
NO