Aztec Catacombs

Indiana Jones는 황금 우상이 있는 고대 Aztec 지하 묘지를 발견했다. 지하 묘지는 n개의 동굴로 이루어져 있다. 동굴의 각 쌍은 열거나 닫을 수 있는 양방향 통로로 연결되어 있다. 지하 묘지의 입구는 동굴 1에 있고, 우상과 출구는 동굴 n에 있다.

When Indiana가 열린 통로를 이용해 동굴 x에서 동굴 y로 이동하면, 동굴 x에 연결된 모든 통로의 상태가 바뀐다. 즉, 열려 있던 모든 통로는 닫히고 닫혀 있던 모든 통로는 열린다. Indiana는 가능한 한 적은 수의 통로를 지나 동굴 1에서 동굴 n로 가려고 한다. 최적의 경로를 찾거나 지하 묘지에서 나가는 것이 불가능한지 판별하도록 도와주자.

첫째 줄에 두 정수 n와 m (2 ≤ n ≤ 3⋅ $10^5$, 0 ≤ m ≤ 3 ⋅ $10^5$)가 주어진다. 이는 각각 동굴의 수와 최초 시점에 열려 있는 통로의 수이다.

다음 m개의 줄에는 열려 있는 통로가 설명된다. 이 줄들 중 i-th 줄에는 두 정수 $u_i$와 $v_i$ (1 ≤ $u_i$, $v_i$ ≤ n, $u_i$ ≠ $v_i$)가 주어진다. 이는 i-th 번째 열린 통로로 연결된 동굴들이다. 동굴의 각 순서 없는 쌍은 최대 한 번만 주어짐이 보장된다.

출구로 가는 경로가 있다면, 첫째 줄에 Indiana가 지나야 하는 통로의 최소 개수인 정수 k (1 ≤ k ≤ $10^6$)를 출력한다. 둘째 줄에 Indiana가 방문해야 하는 순서대로 동굴의 번호를 나타내는 k+1개의 정수 $x_0$, …, $x_k$를 출력한다. 수열 $x_0$, …, $x_k$는 다음 조건을 만족해야 한다.

• $x_0$ = 1, $x_k$ = n;
• 1부터 k까지의 각 i에 대해, Indiana가 해당 통로를 지나는 순간 $x_{i - 1}$에서 $x_i$로 가는 통로가 열려 있어야 한다.

경로가 없다면 정수 -1 하나를 출력한다.

경로가 있다면 $10^6$개 이하의 통로로 이루어진 경로가 존재함을 보일 수 있다.