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$개 이하로 지나는 경로가 존재함을 보일 수 있다.