Aztec Catacombs

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 3\cdot 10^5$$$, $$$0 \leq m \leq 3 \cdot 10^5$$$) — the number of caves and the number of open corridors at the initial moment.

The next $$$m$$$ lines describe the open corridors. The $$$i$$$-th of these lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — the caves connected by the $$$i$$$-th open corridor. It is guaranteed that each unordered pair of caves is presented at most once.

Output:

If there is a path to exit, in the first line print a single integer $$$k$$$ — the minimum number of corridors Indians should pass through ($$$1 \leq k \leq 10^6$$$). In the second line print $$$k+1$$$ integers $$$x_0, \ldots, x_k$$$ — the number of caves in the order Indiana should visit them. The sequence $$$x_0, \ldots, x_k$$$ should satisfy the following:

• $$$x_0 = 1$$$, $$$x_k = n$$$;
• for each $$$i$$$ from $$$1$$$ to $$$k$$$ the corridor from $$$x_{i - 1}$$$ to $$$x_i$$$ should be open at the moment Indiana walks along this corridor.

If there is no path, print a single integer $$$-1$$$.

We can show that if there is a path, there is a path consisting of no more than $$$10^6$$$ corridors.

Sample Input:

4 4
1 2
2 3
1 3
3 4

Sample Output:

2
1 3 4 

Sample Input:

4 2
1 2
2 3

Sample Output:

4
1 2 3 1 4