D. Aztec Catacombs

Codeforces

IDCF925D

Time2000ms

Memory256MB

Difficulty—

constructive algorithms

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]

Samples

Input #1

Output #1

2
1 3 4

Input #2

4 2
1 2
2 3

Output #2

4
1 2 3 1 4

API Response (JSON)

{
  "problem": {
    "name": "D. 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": "CF925D"
  },
  "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"
    }
  ]
}

Full JSON Raw Segments