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 đườ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

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

Dữ liệu ra

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.

Nếu có nhiều hành trình, in ra một hành trình bất kỳ; có thể bắt đầu từ thành phố bất kỳ trên hành trình và đi theo chiều bất kỳ.

Ràng buộc

• $1\le n\le 10000$; $1\le m\le 200000$.
• Mỗi đoạn đường nối hai thành phố khác nhau; không có hai đoạn đường nối cùng một cặp thành phố.

Subtasks

• Subtask 1 ($50\%$ số test): $n\le 500$.
• Subtask 2 ($50\%$ số test): $500<n\le 10000$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ