CF925D.Aztec Catacombs

Indiana Jones found ancient Aztec catacombs containing a golden idol. The catacombs consists of $n$ caves. Each pair of caves is connected with a two-way corridor that can be opened or closed. The entrance to the catacombs is in the cave $1$, the idol and the exit are in the cave $n$.

When Indiana goes from a cave $x$ to a cave $y$ using an open corridor, all corridors connected to the cave $x$ change their state: all open corridors become closed, all closed corridors become open. Indiana wants to go from cave $1$ to cave $n$ going through as small number of corridors as possible. Help him find the optimal path, or determine that it is impossible to get out of catacombs.

印第安纳·琼斯在古老的阿兹特克地下墓穴中发现了一尊黄金神像。该墓穴由 $n$ 个洞穴组成。每对洞穴之间都有一条双向走廊，每条走廊均可开启或关闭。墓穴入口位于洞穴 $1$，而神像与出口则位于洞穴 $n$。

当印第安纳经一条开启的走廊从洞穴 $x$ 前往洞穴 $y$ 时，所有与洞穴 $x$ 相连的走廊状态都会翻转：所有开启的走廊变为关闭，所有关闭的走廊变为开启。印第安纳希望从洞穴 $1$ 出发，以经过尽可能少的走廊为代价抵达洞穴 $n$。请帮助他找出最优路径，或判定无法离开该墓穴。

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.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 3\cdot 10^5$，$0 \leq m \leq 3 \cdot 10^5$），分别表示洞穴的数量以及初始时刻开放的通道数量。

接下来的 $m$ 行描述了开放的通道。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$），表示第 $i$ 条开放通道所连接的两个洞穴。保证每对无序洞穴至多出现一次。

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.

如果存在一条通往出口的路径，则在第一行输出一个整数 $k$ —— 印第安纳需要经过的走廊的最少数量（$1 \leq k \leq 10^6$）。在第二行输出 $k+1$ 个整数 $x_0, \ldots, x_k$ —— 印第安纳应依次访问的洞穴编号。序列 $x_0, \ldots, x_k$ 应满足以下条件：

• $x_0 = 1$，$x_k = n$；
• 对每个 $i$（从 $1$ 到 $k$），当印第安纳沿走廊从 $x_{i - 1}$ 走向 $x_i$ 时，该走廊必须处于开启状态。

若不存在路径，则输出单个整数 $-1$。

可以证明：若存在路径，则必存在一条由不超过 $10^6$ 条走廊组成的路径。