{"problem":{"name":"F. Aztec Catacombs","description":{"content":"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 ent","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF967F"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nWhen 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\n## Input\n\nThe 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.\n\nThe 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\n## Output\n\nIf 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:\n\n*   $x_0 = 1$, $x_k = n$;\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.\n\nIf there is no path, print a single integer $-1$.\n\nWe can show that if there is a path, there is a path consisting of no more than $10^6$ corridors.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"印第安纳·琼斯发现了一座古老的阿兹特克地宫，其中藏有一座金制偶像。地宫由 $n$ 个洞穴组成。每对洞穴之间都有一条双向通道，通道可以处于打开或关闭状态。地宫的入口位于洞穴 $1$，偶像和出口位于洞穴 $n$。\\n\\n当印第安纳从洞穴 $x$ 通过一条打开的通道前往洞穴 $y$ 时，所有与洞穴 $x$ 相连的通道状态都会翻转：所有打开的通道变为关闭，所有关闭的通道变为打开。印第安纳希望从洞穴 $1$ 到达洞穴 $n$，并尽可能少地经过通道。请帮助他找到最优路径，或判断无法离开地宫。\\n\\n第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 3 dot.op 10^5$，$0 lt.eq m lt.eq 3 dot.op 10^5$）——洞穴的数量和初始时刻打开的通道数量。\\n\\n接下来的 $m$ 行描述打开的通道。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 lt.eq u_i, v_i lt.eq n$，$u_i eq.not v_i$）——表示第 $i$ 条打开通道连接的两个洞穴。保证每对无序洞穴至多出现一次。\\n\\n如果存在一条通往出口的路径，则第一行输出一个整数 $k$ —— 印第安纳需要经过的最少通道数（$1 lt.eq k lt.eq 10^6$）。第二行输出 $k + 1$ 个整数 $x_0, dots.h, x_k$ —— 印第安纳应依次访问的洞穴编号。序列 $x_0, dots.h, x_k$ 应满足以下条件：\\n\\n如果不存在路径，则输出一个整数 $-1$。\\n\\n我们可以证明，如果存在路径，则存在一条不超过 $10^6$ 条通道的路径。\"},{\"iden\":\"input\",\"content\":\"第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 3 dot.op 10^5$，$0 lt.eq m lt.eq 3 dot.op 10^5$）——洞穴的数量和初始时刻打开的通道数量。接下来的 $m$ 行描述打开的通道。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 lt.eq u_i, v_i lt.eq n$，$u_i eq.not v_i$）——表示第 $i$ 条打开通道连接的两个洞穴。保证每对无序洞穴至多出现一次。\"},{\"iden\":\"output\",\"content\":\"如果存在一条通往出口的路径，则第一行输出一个整数 $k$ —— 印第安纳需要经过的最少通道数（$1 lt.eq k lt.eq 10^6$）。第二行输出 $k + 1$ 个整数 $x_0, dots.h, x_k$ —— 印第安纳应依次访问的洞穴编号。序列 $x_0, dots.h, x_k$ 应满足以下条件：$x_0 = 1$，$x_k = n$；对于每个 $i$ 从 $1$ 到 $k$，印第安纳经过通道 $x_{i - 1}$ 到 $x_i$ 时，该通道必须处于打开状态。如果不存在路径，则输出一个整数 $-1$。我们可以证明，如果存在路径，则存在一条不超过 $10^6$ 条通道的路径。\"},{\"iden\":\"examples\",\"content\":\"输入\\n4 4\\n1 2\\n2 3\\n1 3\\n3 4\\n输出\\n2\\n1 3 4\\n\\n输入\\n4 2\\n1 2\\n2 3\\n输出\\n4\\n1 2 3 1 4 \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E_0) $ be an undirected graph where:  \n- $ V = \\{1, 2, \\dots, n\\} $ is the set of caves.  \n- $ E_0 \\subseteq \\binom{V}{2} $ is the initial set of open corridors, with $ |E_0| = m $.  \n\nDefine the **state** of the graph as a function $ s: \\binom{V}{2} \\to \\{0,1\\} $, where $ s(e) = 1 $ if corridor $ e $ is open, $ 0 $ if closed. Initially, $ s(e) = 1 $ iff $ e \\in E_0 $.  \n\nA **move** from cave $ x $ to cave $ y $ is valid if $ s(\\{x,y\\}) = 1 $. Upon traversing edge $ \\{x,y\\} $:  \n- For all $ z \\in V \\setminus \\{x\\} $, the state of $ \\{x,z\\} $ flips: $ s(\\{x,z\\}) \\leftarrow 1 - s(\\{x,z\\}) $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 3 \\cdot 10^5 $  \n2. $ 0 \\le m \\le 3 \\cdot 10^5 $  \n3. Initial graph has no multiple edges.  \n4. Path must start at $ x_0 = 1 $, end at $ x_k = n $.  \n5. Path length $ k \\le 10^6 $ if solution exists.  \n\n**Objective**  \nFind the shortest path $ P = (x_0, x_1, \\dots, x_k) $ such that:  \n- $ x_0 = 1 $, $ x_k = n $,  \n- For each $ i \\in \\{1, \\dots, k\\} $, $ \\{x_{i-1}, x_i\\} $ is open in the current state $ s $ before traversal,  \n- After each traversal, the state of all edges incident to $ x_{i-1} $ flips.  \n\nIf no such path exists, output $ -1 $. Otherwise, output $ k $ and the sequence $ x_0, \\dots, x_k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF967F","tags":["graphs"],"sample_group":[["4 4\n1 2\n2 3\n1 3\n3 4","2\n1 3 4"],["4 2\n1 2\n2 3","4\n1 2 3 1 4"]],"created_at":"2026-03-03 11:00:39"}}