CF925D 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$。