Bình đang xây dựng một mạng lưới giao thông liên kết gồm \(N\) trang trại (được đánh số từ \(1\) đến \(N\)) và \(M\) con đường hai chiều trực tiếp nối giữa chúng. Để khảo sát hiện trạng hệ thống giao thông phục vụ vận chuyển nông sản, Bình quyết định đi xe máy xuất phát từ trang trại số 1 và thực hiện quá trình khảo sát theo phương pháp duyệt chiều rộng (BFS).

Quy tắc khảo sát của Bình:

1. Từ một trang trại đang đứng, Bình sẽ ưu tiên đi thăm tất cả các trang trại kề cận chưa được thăm.
2. Nếu có nhiều trang trại kề cạnh có thể đi tiếp, Bình luôn ưu tiên đi tới trang trại có số hiệu nhỏ hơn trước.

Hãy giúp Bình mô phỏng thứ tự các trang trại được khảo sát và tìm đường đi ngắn nhất (chứa ít con đường nhất) từ trang trại 1 đến trang trại \(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ả con đường hai chiều giữa trang trại \(u\) và \(v\).

Định dạng đầu ra

• Dòng thứ nhất: Dãy số nguyên biểu diễn thứ tự các trang trại được Bình khảo sát, cách nhau bởi dấu cách.
• Dòng thứ hai: Dãy số nguyên biểu diễn lộ trình đi qua các trang trại từ 1 đến \(N\) ngắn nhất. Nếu không thể đi tới, in ra -1.

Ví dụ

Input:

4 4
1 2
1 3
2 4
3 4

Output:

1 2 3 4
1 2 4