An đang thám hiểm một hệ thống hầm ngầm khai thác khoáng sản gồm \(N\) hầm lò chứa quặng (được đánh số từ \(1\) đến \(N\)) và \(M\) lối đi ngầm hai chiều nối giữa chúng. An bắt đầu thám hiểm từ hầm lò số 1 và tiến sâu theo thuật toán duyệt chiều sâu (DFS).

Quy tắc thám hiểm của An:

1. Tại mỗi hầm lò, An sẽ tiếp tục đi sâu vào hầm lò kề cạnh chưa được thám hiểm.
2. Nếu có nhiều hầm lò kề cạnh chưa thám hiểm, An luôn ưu tiên chọn hầm lò có số hiệu nhỏ nhất để đi tiếp.

Hãy giúp An mô phỏng thứ tự các hầm lò được thám hiểm và xuất ra đường đi đầu tiên tìm được từ hầm lò 1 đến hầm lò \(N\) theo thuật toán DFS trên.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)) mô tả lối đi vô hướng giữa hầm lò \(u\) và \(v\).

Định dạng đầu ra

• Dòng thứ nhất: Thứ tự các hầm lò được An thám hiểm, cách nhau bởi dấu cách.
• Dòng thứ hai: Dãy số hiệu hầm lò tạo thành đường đi tìm được từ 1 đến \(N\) theo DFS. Nếu không có đường đi, in ra -1.

Ví dụ

Input:

4 4
1 2
1 3
2 4
3 4

Output:

1 2 4 3
1 2 4