F. Уничтожение ребер
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный связный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Ваша цель — уничтожить все ребра данного графа.

Вы можете выбрать любую вершину в качестве начальной и начать ходить от нее по ребрам. Когда вы идете по ребру, вы разрушаете его. Очевидно, что вы не можете пройти по ребру, если оно уже разрушено.

Вы можете выполнить операцию смена режима не более одного раза во время обхода, и эта операция может быть выполнена только тогда, когда вы находитесь в какой-то вершине (вы не можете выполнить ее во время обхода ребра). После смены режима ребра, через которые вы проходите, удаляются следующим образом: первое ребро после смены режима не уничтожается, второе — уничтожается, третье — не уничтожается, четвертое — уничтожается и так далее. Вы не можете переключиться обратно в исходный режим, и вам не нужно выполнять эту операцию, если вы этого не хотите.

Можете ли вы уничтожить все ребра данного графа?

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

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

Затем следуют $$$m$$$ строк, каждая из которых содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — концы $$$i$$$-го ребра.

Эти ребра образуют связный неориентированный граф без кратных ребер.

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

Если невозможно уничтожить все ребра, выведите 0.

В противном случае выведите последовательность ваших действий следующим образом. Сначала выведите $$$k$$$ — количество действий ($$$k \le 2m + 2$$$). Затем выведите саму последовательность, состоящую из $$$k$$$ целых чисел. Первое целое число должно быть индексом стартовой вершины. Затем каждое следующее целое число должно быть либо индексом следующей вершины в вашем обходе, либо $$$-1$$$, если вы используете операцию смена режима. Вы можете использовать операцию смена режима не более одного раза.

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

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