F. Простой путь чётной длины
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан простой неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами.

Путь называется простым, если он не посещает ни одну вершину более одного раза. Длина пути — это число рёбер в нём.

Найдите кратчайший простой путь чётной длины из вершины $$$1$$$ в вершину $$$n$$$ или определите, что такого пути не существует.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2\le n\le 1000$$$, $$$0\le m\le \frac{n(n-1)}2$$$) — количество вершин и количество рёбер в графе.

Далее следуют $$$m$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\ne v_i$$$) — две вершины, которые соединяет $$$i$$$-е ребро.

Гарантируется, что в графе нет петель и кратных рёбер.

Гарантируется, что сумма значений $$$n^3$$$ по всем наборам входных данных не превосходит $$$1000^3$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных, если такого пути не существует, выведите $$$-1$$$.

Иначе выведите любой кратчайший простой путь чётной длины из вершины $$$1$$$ в вершину $$$n$$$:

  • В первой строке выведите его длину $$$k$$$;
  • Во второй строке выведите $$$k+1$$$ вершин $$$p_0,p_1,\ldots,p_k$$$ в порядке следования, где $$$p_0=1$$$ и $$$p_k=n$$$.

Если возможны несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
5
2 0
3 2
1 2
2 3
4 3
1 2
2 3
3 4
5 4
1 5
1 2
2 5
3 4
6 7
1 6
1 2
2 3
3 4
4 6
2 5
4 5
Выходные данные
-1
2
1 2 3
-1
2
1 2 5
4
1 2 3 4 6
Примечание

В первом наборе входных данных пути из вершины $$$1$$$ в вершину $$$2$$$ не существует, поэтому ответа нет.

Во втором наборе входных данных путь $$$1 \to 2 \to 3$$$ имеет длину $$$2$$$, и это кратчайший простой путь чётной длины.

В третьем наборе входных данных единственный простой путь из вершины $$$1$$$ в вершину $$$4$$$ имеет длину $$$3$$$, что нечётно, поэтому ответа нет.

В четвёртом наборе входных данных путь, состоящий только из ребра $$$1 \to 5$$$, имеет длину $$$1$$$, что нечётно и не может быть ответом. Путь $$$1 \to 2 \to 5$$$ имеет длину $$$2$$$.

В пятом наборе входных данных путь $$$1 \to 2 \to 3 \to 4 \to 6$$$ имеет длину $$$4$$$, тогда как путь $$$1 \to 6$$$ имеет длину $$$1$$$, что нечётно.