English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
[{"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 "}]}
**Definitions**
Let $ G = (V, E_0) $ be an undirected graph where:
- $ V = \{1, 2, \dots, n\} $ is the set of caves.
- $ E_0 \subseteq \binom{V}{2} $ is the initial set of open corridors, with $ |E_0| = m $.
Define 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 $.
A **move** from cave $ x $ to cave $ y $ is valid if $ s(\{x,y\}) = 1 $. Upon traversing edge $ \{x,y\} $:
- For all $ z \in V \setminus \{x\} $, the state of $ \{x,z\} $ flips: $ s(\{x,z\}) \leftarrow 1 - s(\{x,z\}) $.
**Constraints**
1. $ 2 \le n \le 3 \cdot 10^5 $
2. $ 0 \le m \le 3 \cdot 10^5 $
3. Initial graph has no multiple edges.
4. Path must start at $ x_0 = 1 $, end at $ x_k = n $.
5. Path length $ k \le 10^6 $ if solution exists.
**Objective**
Find the shortest path $ P = (x_0, x_1, \dots, x_k) $ such that:
- $ x_0 = 1 $, $ x_k = n $,
- For each $ i \in \{1, \dots, k\} $, $ \{x_{i-1}, x_i\} $ is open in the current state $ s $ before traversal,
- After each traversal, the state of all edges incident to $ x_{i-1} $ flips.
If no such path exists, output $ -1 $. Otherwise, output $ k $ and the sequence $ x_0, \dots, x_k $.
API Response (JSON)
{
"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 ent...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"印第安纳·琼斯发现了一座古老的阿兹特克地宫，其中藏有一座金制偶像。地宫由 $n$ 个洞穴组成。每对洞穴之间都有一条双向通道，通道可以处于打开或关闭状态。地宫的入口位于洞穴 $1$，偶像和出口位于洞穴 $n$。\\n\\n当印第安纳从洞穴 $x$ 通过一条打开的通道前往洞穴 $y$ 时，所有与洞穴 $x$ 相连的通道状态都会翻转：所有打开的...",
"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 $...",
"is_translate": false,
"language": "Formal"
}
]
}