← 返回题目列表

Codeforces · 925/D

D. 阿兹特克地下墓穴

中文机器翻译题面 查看原题

印第安纳琼斯发现了古代阿兹特克地下墓穴,里面有一个金色的偶像。地下墓穴由 $$$n$$$ 洞穴组成。每对洞穴均由一条可打开或关闭的双向走廊相连。地下墓穴的入口在洞穴$$$1$$$中,神像和出口在洞穴$$$n$$$中。

当印第安纳使用开放走廊从洞穴 $$$x$$$ 前往洞穴 $$$y$$$ 时,连接到洞穴 $$$x$$$ 的所有走廊都会更改其状态:所有开放走廊变为关闭,所有封闭走廊变为开放。印第安纳想要从 $$$1$$$ 洞穴到 $$$n$$$ 洞穴,穿过尽可能少的走廊。帮助他找到最佳路径,或者确定不可能走出地下墓穴。

输入

第一行包含两个整数 $$$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$$$ 开放走廊连接的洞穴。保证每对无序洞穴最多出现一次。

输出

如果有一条出口路径,则在第一行打印一个整数 $$$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$$$;
- 对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$,从 $$$x_{i - 1}$$$ 到 $$$x_i$$$ 的走廊应该在印第安纳沿着这条走廊行走时开放。

如果没有路径,则打印单个整数 $$$-1$$$。

我们可以证明,如果存在一条路径,则存在一条由不超过 $$$10^6$$$ 走廊组成的路径。

示例

输入 #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