#531. ACIRCLE – Tìm kiếm chu trình

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài
Đưa lên bởi: Chùm CUỐI

Đề bài

Một khu du lịch có n địa điểm đánh số 1, 2, ..., n và một số đường đi hai chiều nối những cặp địa điểm đó. Giữa hai địa điểm bất kỳ có nhiều nhất là một đường đi nối chúng.

Một khách du lịch xuất phát từ địa điểm S muốn đi thăm một số địa điểm khác rồi sau đó quay trở về S . Để tránh sự nhàm chán, ông ta muốn tìm một hành trình không qua một con đường hay một địa điểm nào quá một lần (Tất nhiên, ngoại trừ địa điểm S phải có mặt trong hành trình hai lần bởi đó là nơi bắt đầu cũng như kết thúc hành trình).

Yêu cầu: Hãy chỉ đường cho du khách đó.

Dữ liệu vào:

  • Dòng đầu chứa hai số n, S ;
  • Các dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v cho ta thông tin: giữa hai địa điểm u v có một đường đi hai chiều nối chúng.

Dữ liệu ra:

  • Dòng đầu ghi từ YES hay NO tuỳ theo có tồn tại hành trình thoả mãn yêu cầu của du khách hay không;
  • Nếu dòng đầu ghi từ YESthì dòng thứ hai ghi hành trình tìm được: Bắt đầu là địa điểm S , tiếp theo là danh sách các địa điểm sẽ đi qua theo đúng thứ tự trong hành trình, cuối cùng lại là địa điểm S .

Ví dụ:

Dữ liệu vào:
7 1
1 2
1 5
1 7
2 3
2 4
3 4
5 6
6 7
Dữ liệu ra:
YES
1 7 6 5 1

Giới hạn:

  • 3 ≤ n ≤ 200; 1 ≤ S ≤ n .