Đường đi của tin nhắn

Trong một dự án phát triển hệ thống mạng, FullHouse Dev được giao nhiệm vụ phân tích khả năng kết nối giữa các máy tính trong mạng của công ty Syrjälä. Họ cần xác định liệu Uolevi có thể gửi tin nhắn đến Maija hay không, và nếu có thể, tìm ra đường đi ngắn nhất giữa hai máy tính này.

Bài toán

Mạng máy tính có \(n\) máy tính và \(m\) kết nối. FullHouse Dev cần tìm ra liệu Uolevi có thể gửi tin nhắn đến Maija hay không, và nếu có thể, số lượng máy tính tối thiểu trên đường đi đó là bao nhiêu.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng máy tính và số kết nối. Các máy tính được đánh số từ \(1\) đến \(n\). Máy tính của Uolevi là số \(1\) và máy tính của Maija là số \(n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): thể hiện có kết nối giữa hai máy tính này.
• Mỗi kết nối nối hai máy tính khác nhau, và giữa hai máy tính bất kỳ chỉ có tối đa một kết nối.

OUTPUT FORMAT:

• Nếu có thể gửi tin nhắn, đầu tiên in ra \(k\): số lượng máy tính tối thiểu trên đường đi hợp lệ. Sau đó, in ra một ví dụ về đường đi đó. Bạn có thể in ra bất kỳ đường đi hợp lệ nào.
• Nếu không có đường đi nào, in ra "IMPOSSIBLE".

Ràng buộc:

• \(2 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)

Ví dụ

INPUT

5 5
1 2
1 3
1 4
2 3
5 4

OUTPUT

3
1 4 5

Giải thích

Trong ví dụ này, đường đi ngắn nhất từ máy tính 1 (Uolevi) đến máy tính 5 (Maija) đi qua 3 máy tính: 1 → 4 → 5. Đây là đường đi tối ưu vì không có cách nào để đi từ máy tính 1 đến máy tính 5 mà dùng ít máy tính hơn.