Thành phố Mexico được xây dựng trong một thung lũng đẹp mang tên Thung lũng Mexico, nơi phần lớn diện tích trước kia là một hồ nước. Khoảng năm 1300, các thủ lĩnh tôn giáo Aztec ra lệnh san lấp phần giữa hồ để xây dựng kinh đô của đế chế. Ngày nay, hồ đã bị lấp hoàn toàn.

Trước khi người Aztec đến, có \(c\) thành phố nằm trên bờ, xung quanh hồ. Một số cặp thành phố thiết lập thỏa thuận thương mại và vận chuyển hàng hóa qua lại bằng thuyền. Có thể nối hai thành phố bất kỳ bằng một đoạn thẳng đi qua hồ.

Các vị vua quyết định tổ chức lại hoạt động buôn bán bằng một tuyến đường thương mại nối tất cả các thành phố quanh hồ. Tuyến đường phải thỏa mãn các yêu cầu sau:

• Bắt đầu tại một thành phố bất kỳ, đi qua tất cả các thành phố, rồi kết thúc tại một thành phố khác với thành phố xuất phát.
• Mỗi thành phố được ghé thăm đúng một lần.
• Hai thành phố được ghé thăm liên tiếp phải có thỏa thuận thương mại với nhau.
• Mỗi chặng giữa hai thành phố liên tiếp là một đoạn thẳng.
• Tuyến đường không được tự cắt, nhằm tránh va chạm giữa các thuyền.

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

Trong hình, cả nét đậm và nét mảnh đều biểu diễn các thỏa thuận thương mại. Các nét đậm tạo thành một tuyến đường bắt đầu ở thành phố \(2\) và kết thúc ở thành phố \(5\). Tuyến này không tự cắt. Ngược lại, một tuyến đi lần lượt qua \(2,6,5,1\) là không hợp lệ vì các chặng của nó cắt nhau.

Cho số thành phố và danh sách các thỏa thuận thương mại, hãy xây dựng một tuyến đường thỏa mãn tất cả các yêu cầu trên, hoặc xác định rằng không thể xây dựng được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(c\), là số thành phố.
• Dòng thứ hai chứa số nguyên \(n\), là số thỏa thuận thương mại.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên phân cách bởi một dấu cách, là số hiệu hai thành phố có thỏa thuận với nhau. Mỗi thỏa thuận chỉ xuất hiện một lần.

Dữ liệu ra

Nếu tồn tại tuyến đường hợp lệ, ghi ra đầu ra chuẩn \(c\) dòng, mỗi dòng chứa một số nguyên là số hiệu thành phố được ghé thăm, theo đúng thứ tự của tuyến đường. Nếu không tồn tại, ghi một dòng chứa -1.

Nếu có nhiều tuyến đường hợp lệ, có thể xuất bất kỳ tuyến nào.

Ràng buộc

• \(3\le c\le1000\).
• Các số hiệu thành phố thuộc đoạn từ \(1\) đến \(c\).

Chấm điểm

Trong các bộ dữ liệu có tổng cộng \(40\) điểm, \(3\le c\le20\).

Ví dụ

7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7

2
3
4
1
7
6
5

Nguồn

IOI 2006.