{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"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.\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."},{"iden":"output","content":"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:\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."},{"iden":"examples","content":"Input\n\n4 4\n1 2\n2 3\n1 3\n3 4\n\nOutput\n\n2\n1 3 4 \n\nInput\n\n4 2\n1 2\n2 3\n\nOutput\n\n4\n1 2 3 1 4"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}