Thi thử Duyên hải 2021 - Lần 3 - Bài 4 - TELEPORTS

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ở 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

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • 1
    ktuan   commented on May 25, 2021, 8:55 p.m.

    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?


  • 3
    I_love_Hoang_Yen   commented on May 8, 2021, 11:50 p.m.

    Bài này hiện không có trình chấm


    • 2
      leduykhongngu   commented on May 14, 2021, 9:41 p.m.

      Em vừa thêm và rejudge lại rồi :3