Đề thi chọn học sinh giỏi cấp Quốc gia THPT môn Tin học

(Bản scan)

Bài 2. (7 đểm) Hành trình du lịch
Công ty du lịch tư nhân Travel chuyên tổ chức các tour du lịch nội địa. Có n thành phó nằm trong
phạm vi khai thác của công ty. Các thành phố được đánh số từ 1 đến n. Có m cặp thành phố có
đoạn đường hai chiều trực tiếp nói chúng. Để đáp ứng yêu cầu của khách hàng trong các kỳ nghỉ
ngắn hạn, công ty chỉ khai thác các tour đi vòng quanh 4 thành phố theo các đoạn dường trực tiếp
nỗi chúng. Để chắc chắn có thể khai thác những tour như vậy, công ty tiến hành khảo sát xem liệu
có 4 thành phố nào tạo thành một hành trình khép kín xuất phát từ một thành phố đi qua 3 thành
phố còn lại, mỗi thành phố đúng một lần và quay về thành phố xuất phát hay không.
Yêu cầu: Hãy giúp công ty kiểm tra xem có tổn tại hành trình nào như vậy hay không.
Dữ liệu: Vào từ file văn bản TRAVEL.INP

Dòng thứ nhất chứa hai số nguyên dương  m (n < 10000; m < 200000);

Dòng thứ i trong số m dòng tiếp theo chứa 2 số là chỉ số 2 thành phố có đoạn đường trực

tiếp nối chúng;
Các số trên cùng một dòng được ghi cách nhau ít nhất một đấu cách.