Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOSTRAVL - Du lịch


Đất nước Monterey có rất nhiều danh lam thánh cảnh đẹp. Brogan đã lên kế hoạch cho chuyến du lịch sắp tới của mình ở Monterey. Theo kế hoạch, Brogan sẽ đi tham quan K danh lam thánh cảnh đẹp nhất ở Monterey. Nhưng Brogan vẫn chưa biết chọn lộ trình sao cho hợp lý. Brogan muốn lộ trình sẽ không đi qua một con đường theo cùng một chiều quá 1 lần và khi kết thúc lộ trình Brogan phải quay về thành phố lúc ban đầu. Ban đầu, Brogan ở thành phố S.

Hãy kiểm tra xem Brogan có thể tìm được lộ trình thỏa các điều kiện trên hay không. Nếu không tồn tại lộ trình như trên thì xuất ra “NIE” còn nếu tồn tại thì xuất ra  “TAK” và một lộ trình bất kỳ thỏa mản yêu cầu trên.

DỮ LIỆU VÀO

  • Dòng đầu tiên chứa 3 số nguyên N, M, S, K lần lượt là số lượng thành phố ở Monterey,  số lượng đường đi ở Monterey, thành phố hiện giờ Brogan ở và số lượng danh lam thánh cảnh mà Brogan muốn tham quan.
  • M dòng tiếp theo mỗi dòng chứa hai số u, v  có nghĩa là có đương đi hai chiều từ thành phố u tới thành phố v.
  • Dòng tiếp theo chứa K số là gồm thử tự của những thành phố mà Brogan muốn tham quan.
  • Lưu ý: đồ thị nhập vào đảm bảo là đồ thị đơn.

DỮ LIỆU RA

  • Dòng đầu tiên chứa “NIE” hoặc “TAK”.
  • Nếu là “TAK”, dòng tiếp theo se chứa số nguyên D là số lượng thành phố nằm trên lộ trình kể cả thành phố xuất phát. Theo sau số D sẽ là dãy gồm D số miêu tả lộ trình tìm được.

RÀNG BUỘC

  • N, M <= 106.
  • K <= N.
  • 10% số test M <= 10.
  • 20% số test đồ thị không có chu trình.

 

VÍ DỤ

                                                                                 

Input

Output

3 2 1 1

1 2

2 3

3

TAK

5 1 2 3 2 1

Giải thích: ta không thể chọn lộ trình 1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 1 vì đoạn đường 1-> 2 đi qua 2 lần theo cùng một chiều từ 1 sang 2.



Được gửi lên bởi:Alex & Friends
Ngày:2014-09-28
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOS Round 28 - Trần Phan Anh Khoa

hide comments
2015-01-19 10:54:21 Bee
"Đạt yêu cầu" và "100" thi cái nào hơn vậy các bác.
2014-10-08 17:49:18 [KC]★★★★*-RAMEN
bài này mình làm LCA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.