D. Ацтекские катакомбы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Индиана Джонс нашел древние ацтекские катакомбы, в которых спрятан золотой идол. Катакомбы состоят из $$$n$$$ пещер. Каждая пара пещер соединена двусторонним коридором, который может быть открыт или закрыт. Вход в катакомбы находится в пещере $$$1$$$, а идол и выход из катакомб — в пещере $$$n$$$.

Когда Индиана переходит из пещеры $$$x$$$ в пещеру $$$y$$$ по открытому коридору, все коридоры, связанные с пещерой $$$x$$$, меняют свое состояние: все ранее открытые коридоры закрываются, а все закрытые — открываются. Цель Индианы — попасть из пещеры $$$1$$$ в пещеру $$$n$$$ за наименьшее число переходов. Помогите ему найти оптимальный маршрут, или определите, что выйти из катакомб невозможно.

Входные данные

В первой строке находится два целых числа $$$n$$$ и $$$m$$$ — количество пещер и количество коридоров, которые открыты в момент входа в катакомбы ($$$2 \leq n \leq 3\cdot 10^5$$$, $$$0 \leq m \leq 3 \cdot 10^5$$$).

Следующие $$$m$$$ строк описывают открытые коридоры. $$$i$$$-я из этих строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ — номера пещер, соединенных $$$i$$$-м открытым коридором ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$). Гарантируется, что каждая неупорядоченная пара пещер упоминается во входе не более одного раза.

Выходные данные

Если искомый маршрут существует, в первой строке выведите одно целое число $$$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$$$ переходов.

Примеры
Входные данные
4 4
1 2
2 3
1 3
3 4
Выходные данные
2
1 3 4
Входные данные
4 2
1 2
2 3
Выходные данные
4
1 2 3 1 4