Thi thử Duyên hải 2021 - Lần 3 - Bài 4 - TELEPORTS
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Ở một thành phố, trò chơi thoát khỏi mê cung hiện đang rất phổ biến. Mê cung gồm ~n~ căn phòng nối với nhau bởi ~m~ hành lang. Ngoài ra, người ta còn bố trí thêm ~k~ cổng dịch chuyển tức thời. Giả sử có một cổng kết nối phòng ~A~ với phòng ~B~ thì ngay sau khi người chơi đi qua một hành lang để đến phòng ~A~ thì sẽ ngay lập tức bị dịch chuyển sang phòng ~B~. Từ phòng ~B~, người chơi có thể tiếp tục di chuyển theo một hành lang nối với nó. Tương tự, khi người chơi di chuyển qua một hành lang đến phòng ~B~ thì sẽ ngay lập tức bị dịch chuyển sang phòng ~A~ và phải đi tiếp qua một hành lang nối với phòng ~A~.
Người chơi được quyền chọn bắt đầu từ một phòng bất kì. Sau đó phải đi qua mỗi hành lang đúng một lần và dừng chân tại một căn phòng bất kì. An chuẩn bị đi chơi trò này và cậu ấy đã biết bản đồ mê cung. Hãy giúp An chiến thắng trò chơi.
Input
Gồm nhiều test, mỗi test bắt đầu bằng một dòng chứa ba số nguyên ~n~, ~m~ và ~k~ ~(1 \leq n~, ~m \leq 100000~; ~0 \leq k \leq 100000)~.
~m~ dòng sau mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 \leq u~, ~v \leq n~; ~u~ ≠ ~v)~ cho biết có hành lang nối hai phòng ~u~ và ~v~.
~k~ dòng sau mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 \leq u~, ~v \leq n~; ~u~ ≠ ~v)~ cho biết có cổng dịch chuyển tức thời kết nối hai phòng ~u~ và ~v~. Mỗi phòng có cổng kết nối tức thời kết nối với tối đa một phòng khác.
Tổng ~n~, tổng ~m~ và tổng ~k~ trong tất cả các test không vượt quá ~100000~. Dữ liệu kết thúc bởi một dòng chứa ba số ~0~.
Output
Với mỗi test, nếu An có thể thắng trò chơi, ghi ra một dòng chứa từ Yes, sau đó là một dòng chứa ~m~ số nguyên cho
biết chỉ số các hành lang mà An lần lượt đi qua. Các hành lang được đánh số từ ~1~ đến ~m~ theo thứ tự xuất hiện trong
dữ liệu. Nếu An không thể thắng trò chơi, ghi ra một dòng duy nhất chứa từ No.
Sample Input
4 2 1
1 2
3 4
3 4
4 3 1
1 2
2 3
3 4
1 4
8 10 1
1 3
1 2
3 4
2 4
4 5
2 5
5 7
5 6
6 8
7 8
1 8
0 0 0
Sample Output
No
Yes
1 2 3
Yes
4 3 1 10 7 6 2 9 8 5
Bình luận
Bài này cho mình test mình wa được không nhỉ admin? Để xem mình xét thiếu trường hợp nào?
Bài này hiện không có trình chấm
Em vừa thêm và rejudge lại rồi :3