Индиана Джонс нашел древние ацтекские катакомбы, в которых спрятан золотой идол. Катакомбы состоят из \(n\) пещер. Каждая пара пещер соединена двусторонним коридором, который может быть открыт или закрыт. Вход в катакомбы находится в пещере \(1\), а идол и выход из катакомб — в пещере \(n\).
Когда Индиана переходит из пещеры \(x\) в пещеру \(y\) по открытому коридору, все коридоры, связанные с пещерой \(x\), меняют свое состояние: все ранее открытые коридоры закрываются, а все закрытые — открываются. Цель Индианы — попасть из пещеры \(1\) в пещеру \(n\) за наименьшее число переходов. Помогите ему найти оптимальный маршрут, или определите, что выйти из катакомб невозможно.
Выходные данные
Если искомый маршрут существует, в первой строке выведите одно целое число \(k\) — минимальное число переходов (\(1 \leq k \leq 10^6\)). Во второй строке выведите \(k+1\) число \(x_0, \ldots, x_k\) — номера пещер в порядке посещения Индианой. Последовательность \(x_0, \ldots, x_k\) должна удовлетворять следующим свойствам:
- \(x_0 = 1\), \(x_k = n\);
- для любого \(i\) от \(1\) до \(k\) коридор из \(x_{i - 1}\) в \(x_i\) должен быть открыт в тот момент, когда Индиана собирается по нему перейти.
Если маршрута не существует, выведите одно число \(-1\).
Гарантируется, что если маршрут существует, то существует и маршрут, состоящий из не более, чем \(10^6\) переходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2
2 3
1 3
3 4
|
2
1 3 4
|
|
2
|
4 2
1 2
2 3
|
4
1 2 3 1 4
|