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.|

TRAVEL12 - VOI 2012 Hành trình du lịch

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/travel12


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 đườ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.
Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 500.

Input

  • Dòng thứ nhất chứa hai số nguyên dương n,m (n ≤ 10000; m ≤ 200000)
  • Dong 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

Output

Ghi ra 4 số nguyên dương theo thứ tự là 4 thành phố trên một hành trình tìm được hoặc ghi số -1 nếu câu trả lời là phủ định.

Example

Input:
5 6
1 2
1 5
2 3
2 5
3 4
4 5 Output: 4 5 2 3

Được gửi lên bởi:VOJ Team
Ngày:2012-01-17
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:VOI 2012

hide comments
2014-12-26 17:09:13 Duc M. Pham
Trả lời bạn ở dưới : Nếu có nhiều đáp án thì in ra một đáp án bất kỳ theo thứ tự bất kỳ nhé bạn :D

Bài này làm xong thì thấy nó rất đơn giản :3
2014-12-26 06:13:37 never give up !!
test ví dụ xuất ra 2 5 4 3 được không?
2014-12-24 01:17:15 ChienTran
65 :(
2014-12-22 10:36:00 giaosudauto
Quá đơn giản!!!
2014-11-20 15:04:38 Dương Bảo
dùng vector không AC, phải code ds kề mới AC @@
2014-09-15 16:20:41 No One
DFS trâu là đc 90 r :) làm sao lên 100 đây >"<
2014-07-25 13:22:10 Thcs Ðặng Chánh Kỷ
đổi kiểu dfs mà cũng chỉ đc 90, khó quá

Last edit: 2014-07-25 17:37:06
2014-07-24 18:01:18 Thcs Ðặng Chánh Kỷ
80 1 lần dfs, làm sao để lên 90 hay 100 đây
2014-02-06 03:52:20 Xiao Lang
DFS trâu đc 90 điểm :3
2014-01-01 05:53:51 Nguyễn Trọng Ðoan
75d :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.