Aztec Catacombs

题意翻译

### 题目描述 一位探险者发现了古代阿兹特克人的地下墓穴，里面有一个金色的神像。地下墓穴由 $n$ 个密室组成。每对密室都连接着一条**双向**走廊，走廊有开放和封闭两种状态。墓穴的入口在 $1$ 号密室，神像和出口在 $n$ 号密室。 当探险者从 $x$ 密室经过开放的走廊进入 $y$ 密室时，与 $x$ 密室相连的所有走廊都会改变其状态（所有开放的走廊都会封闭，所有封闭的走廊都会打开）。探险者希望从 $1$ 号密室穿过尽可能少的走廊到达 $n$ 号密室。请你帮助他找到最佳路径，或者确定不可能走出地下墓穴。 ### 输入格式 第 $1$ 行两个整数 $n$ 、 $m$ ，表示密室的数量和走廊的数量。 接下来 $m$ 行，第 $i$ 行两个整数 $u_i$ 和 $v_i$ ，表示 $u_i$ 和 $v_i$ 密室之间有一条走廊。 ### 输出格式 如果探险者能走出地下墓穴，第 $1$ 行输出通过的最少走廊数量，第 $2$ 行按顺序输出通过的密室编号。 如果探险者走不出地下墓穴，请输出 $-1$ 。 ### 说明/提示 $2 \leq n \leq 3 \cdot 10^5$ $0 \leq m \leq 3 \cdot 10^5$ 数据保证没有重复的走廊 可以证明，路径长度一定不大于 $10^6$。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

4 4
1 2
2 3
1 3
3 4

输出样例 #1

2
1 3 4 

输入样例 #2

4 2
1 2
2 3

输出样例 #2

4
1 2 3 1 4