Лабиринт Кошмаров
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пытаясь спасти своего друга, Уэнсдей оказывается в Лабиринте Кошмаров, созданном древним проклятием. Структура лабиринта представляет собой дерево из $$$n$$$ комнат и $$$n-1$$$ коридоров между ними. Каждая комната имеет уникальный номер от $$$1$$$ до $$$n$$$.

Проклятие, наложенное на лабиринт, искажает пространство так, что Уэнсдей способна из своей текущей комнаты переместиться не только в соседние комнаты, но и все комнаты, до которых можно дойти, пройдя не более трёх коридоров. Иначе говоря, если кратчайший путь между двумя комнатами в лабиринте состоит не более чем из трёх коридоров, то Уэнсдей способна сразу перемещаться между этими комнатами, минуя другие.

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

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

В первой строке задано целое число $$$n$$$ — количество комнат в Лабиринте Кошмаров ($$$3 \le n \le 2 \cdot 10^5$$$). Каждая из следующих $$$n-1$$$ строк содержит пару целых чисел $$$u$$$ и $$$v$$$, означающую, что между комнатами $$$u$$$ и $$$v$$$ существует коридор ($$$1 \le u, v \le 2 \cdot 10^5$$$).

Гарантируется, что лабиринт является деревом.

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

Выведите последовательность комнат — маршрут Уэнсдей.

Примеры

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

    31 22 3

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

    1 3 2 1

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

    91 22 37 58 76 94 72 68 2

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

    1 3 6 9 8 5 4 7 2 1