Mô tả và yêu cầu

Du lịch Đông Tây.
Bạn là người thắng cuộc trong một cuộc thi do một hãng hàng không tài trợ và phần thưởng
là một chuyến du lịch do bạn tuỳ chọn. Có n thành phố và chúng được đánh số từ 1 tới n
theo vị trí từ Tây sang Đông (không có hai thành phố nào ở cùng kinh độ), giữa hai thành
phố có thể có một tuyến bay hai chiều do hãng quản lý. Chuyến du lịch của bạn phải xuất
phát từ thành phố 1, bay theo các tuyến bay của hãng tới thành phố n và chỉ được bay từ
Tây sang Đông, sau đó lại bay theo các tuyến bay của hãng về thành phố 1 và chỉ được bay
từ Đông sang Tây. Hành trình không được thăm bất kỳ thành phố nào quá một lần, ngoại
trừ thành phố 1 là nơi bắt đầu và kết thúc hành trình.
Yêu cầu: đặt ra là tìm hành trình du lịch qua nhiều thành phố nhất.
Dữ liệu: vào từ file văn bản EWTOUR.INP gồm:
Dòng 1 chứa số thành phố ( ) và số tuyến bay (𝑚), 3 ≤ 𝑛 ≤ 200; 𝑚 ≤ 20000
dòng tiếp, mỗi dòng chứa thông tin về một tuyến bay: gồm chỉ số hai thành phố
tương ứng với tuyến bay đó.
Kết quả: ghi vào file văn bản EWTOUR.OUT gồm:
Nếu không tồn tại hành trình theo yêu cầu, ghi ra số -1.
Nếu tồn tại hành trình theo yêu cầu, dòng 1 ghi số thành phố đi qua trong hành trình,
dòng 2 ghi các thành phố theo hành trình tìm được, bắt đầu từ thành phố 1, kết thúc ở thành
phố 1.

Ví dụ

EWTOUR.INP               EWTOUR.OUT
                             5 6                       4
                             1 2                       1 2 5 4 1
                             2 3
                             3 4
                             4 5
                             1 4
                             2 5