Olympiad in Informatics

Thung lũng Mehico

Thành phố Mehico được xây dựng trên một thung lũng rất đẹp được gọi là Thung lũng Mehico. Trước đây thung lũng này thực chất là một cái hồ nước lớn. Vào khoảng năm 1300, trong triều đại Aztec đã quyết định cho lấp thung lũng này để xây dựng thủ đô.

Trước đó, xung quanh thung lũng này người ta xây dựng các thành phố. Một số thành phố này có quan hệ buôn bán hàng hóa với nhau bằng thuyền. Như vậy có thể kết nối hai thành phố có quan hệ bằng một đoạn thẳng nối xuyên qua thung lũng.

Các thị trưởng các thành phố ven thung lũng quyết định xây dựng một con đường buôn bán để kết nối tất cả các thành phố ven thung lũng. Con đường này sẽ phải thỏa mãn các điều kiện sau:

• Con đường bắt đầu từ một thành phố bất kỳ, đi qua tất cả các thành phố và kết thúc tại một thành phố khác với thành phố xuất phát.
• Con đường đi qua mỗi thành phố đúng một lần.
• Mỗi cặp thành phố liền nhau trên con đường buôn bán đều có quan hệ kết nối với nhau trước đó.
• Mỗi cặp thành phố liền nhau trên đường đi sẽ được nối bằng một đoạn thẳng.
• Đường đi không bao giờ tự giao nhau.

Hình trên mô tả thung lũng và các thành phố bao quanh. Các đoạn thẳng (đường mảnh cũng như đậm) là các kết nối buôn bán giữa các thành phố. Con đường buôn bán được xây dựng xuất phát từ thành phố 2 và kết thúc tại thành phố 5 và được mô tả bằng nét đậm.

Con đường này không tự cắt. Nếu ta đi từ 2 đến 6, sau đó đến 5, sau đó là 1 thì sẽ không hợp lệ vì tự cắt.

Các thành phố được đánh số từ 1 theo chiều kim đồng hồ.

Yêu cầu

Viết chương trình, cho trước số lượng thành phố và danh sách các kết nối giữa chúng, chỉ ra cách xây dựng con đường buôn bán thỏa mãn yêu cầu.

Ràng buộc

3 ≤ c ≤ 1000, Số lượng thành phố ven hồ.

Dữ liệu

Dòng 1: Chứa số tự nhiên c

Dòng 2: Chứa số tự nhiên n là số các kết nối buôn bán giữa các thành phố ven hồ.

n dòng tiếp theo: Mỗi dòng chứa đúng một kết nối buôn bán. Chứa hai số tự nhiên cách nhau bởi một dấu cách.

Dữ liệu mẫu
7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7

Kết quả

Nếu có thể xây dựng được con đường buôn bán, viết ra c dòng, mỗi dòng là một số tự nhiên chỉ ra thứ tự các thành phố cần đi qua trên con đường.

Nếu không thể xây dựng con đường như vậy thì viết ra số -1.

Chú ý: Nếu tồn tại nhiều con đường, chỉ cần chỉ ra một trong chúng.

Kết quả mẫu
2
3
4
1
7
6
5

Cách chấm điểm

Với một số lượng Test với tổng điểm 40, các test đều thỏa mãn: 3 ≤ c ≤ 20