Aztec Catacombs
Contest: VK Cup 2018 - Round 3
Difficulty rating: 2600
Tags: 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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4 4
1 2
2 3
1 3
3 4

Example output:
2
1 3 4

Example input:
4 2
1 2
2 3

Example output:
4
1 2 3 1 4

Editorial:
Let us formualate a problem in terms of graph theory and make some observation. Denote the start and the finish vertices as $$$s$$$ and $$$t$$$.
Observation 1. If vertices $$$s$$$ and $$$t$$$ are connected with a simple path consisting of $$$k$$$ edges, then by the statement of the problem Indiana Johns may use it leading us to the answer of length $$$k$$$. Thus, the answer does not exceed $$$d$$$ where $$$d$$$ is the length of the shortest path between $$$s$$$ and $$$t$$$ if $$$s$$$ and $$$t$$$ are connected and $$$\infty$$$ otherwise. Let us call path consisting only of the original edges of the graph trivial and the paths including originally non-existent edges non-trivial.
Observation 2. The length of any non-trivial path is at least 4. Indeed, let $$$s = v_0 \xrightarrow{e_1} v_2 \xrightarrow{e_2} \cdots \xrightarrow{e_k} v_k = t$$$ be the valid path in which some of the edges $$$e_i$$$ is missing in the original graph. Notice that the edge $$$e_1$$$ may not be missing as by the moment we follow it, nothing was flipped yet, and $$$e_2$$$ also may not be missing as it requires $$$e_2$$$ to be same with $$$e_1$$$ which was just flipped. Also note that $$$e_3$$$ may not be the last edge in our path because otherwise it must be missing in the original graph (since the path is non-trivial), and we did not visit vertex $$$v_2$$$ yet as $$$v_2 \neq v_1$$$ and $$$v_2 \neq v_0 = 1$$$. Thus, $$$k \geq 4$$$.
Observation 3. If $$$d \leq 4$$$, then the answer is $$$d$$$. It immediately follows from two previous observations: shortest trivial path has the length of $$$d$$$ and shortest non-trivial has the length of at least $$$4$$$.
Наблюдение 4. If $$$d \geq 4$$$ and there exists a vertex $$$v_2$$$ at the distance of $$$2$$$ from $$$v_0 = s$$$, then there exists a non-trivial path of length $$$4$$$. Indeed, $$$v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow v_0 \rightarrow t$$$ is such path where $$$v_1$$$ is a vertex through which the path of length $$$2$$$ between $$$v_0$$$ and $$$v_2$$$ passes. Finally, note that $$$v_2$$$ and $$$v_0$$$ are not initially connected (otherwise the distance between $$$v_0$$$ and $$$v_2$$$ would be 1), hence when we visit $$$v_2$$$, the edge $$$v_2 \rightarrow v_0$$$ is present. Similarly, by the moment of second visit of vertex $$$v_0$$$ originally missing edge $$$v_0 \rightarrow t$$$ appears.
Observation 5. Any non-trivial path of length $$$4$$$ looks exactly as described in an observation 4, first two initially existent edges, then newly appeared edge leading to $$$s$$$ and finally newly appeared edge leading to $$$t$$$. It immediately follows from the explanation of the observation 2.
Observation 6. If $$$d \geq 4$$$ and there no vertex $$$v_2$$$ located at the distance $$$2$$$ from $$$s$$$, then $$$s$$$ is connected with all vertices in its connected component and this component does not contain $$$t$$$.
Observation 7. If, under conditions of the previous observation, it we remove vertex $$$s$$$, then all the vertices initially adjacent to it will be distributed into several connected components. If all connected components are cliques, there are no valid paths. Indeed, after first transition we get into some clique and then we may only move inside it and it keeps shrinking until we get to an isolated vertex from which we can not go anywhere.
Observation 8. If any of the connected components adjacent with $$$s$$$ is not a clique, then the shortest valid non-trivial path has a length of $$$5$$$. Indeed, consider a connected component $$$C$$$ initially connected with $$$s$$$ that is not a clique. It is not a clique, hence it contains a vertex $$$v_1$$$ of degree less than $$$|C| - 1$$$. This vertex is not connected with a whole component $$$C$$$, thus there are vertices $$$v_2, v_3 \in C$$$ such that $$$v_3$$$ is not connected with $$$v_1$$$, while $$$v_1$$$ and $$$v_2$$$ are connected and $$$v_2$$$ and $$$v_3$$$ are also connected with an edge. It means that there is a non-trivial path $$$v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_1 \rightarrow t$$$.
The observations above cover all possible cases in this problem and also yield a solution working in linear time in terms of a size of the original graph.