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

Input

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

Output

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.

Giới hạn

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

Sample Input

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

Sample Output

2
3
4
1
7
6
5