TELEPORTS (DHBB 2021 T.Thử)

Xem PDF

Điểm: 750 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ở 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\)\(k\) (\(1 ≤ n, m ≤ 100000; 0 ≤ k ≤ 100000\)).
    • \(m\) dòng sau mỗi dòng chứa hai số nguyên \(u\)\(v\) (\(1 ≤ u, v ≤ n; u ≠ v\)) cho biết có hành lang nối hai phòng \(u\)\(v\).
    • \(k\) dòng sau mỗi dòng chứa hai số nguyên \(u\)\(v\) (\(1 ≤ u, v ≤ 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\). 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

Example

Test 1

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
Output
No 
Yes 
1 2 3 
Yes 
4 3 1 10 7 6 2 9 8 5
Note

Bình luận


  • 0
    huyhau6a2    10:11 a.m. 16 Tháng 10, 2022

    đề ghi YES NO mà oup lại ghi Yes No hmm


    • 0
      tuank99lhp    2:00 p.m. 18 Tháng 6, 2021

      ad ơi bài này ko có trình chấm :<


      • 3
        BETTER    7:14 a.m. 10 Tháng 5, 2021

        AI cho em xin link đề với ạ?