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

Ася очень любит животных. Недавно она приобрела $$$n$$$ котят, пронумеровала их от $$$1$$$ до $$$n$$$ и поселила в вольере. Вольер представляет собой ряд из $$$n$$$ ячеек, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Cоседние ячейки разделены сетчатыми перегородками, всего в вольере $$$n - 1$$$ перегородок. Изначально в каждой ячейке поселился ровно один котёнок с некоторым номером.

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

  • Обратила внимание, что котята $$$x_i$$$ и $$$y_i$$$, живущие в соседних ячейках, хотят играть вместе.
  • Удаляла перегородку между этими ячейками, превращая их в одну, в которой оказывались все котята из двух прежних ячеек.

Поскольку Ася ни разу возвращала перегородки, через $$$n - 1$$$ день вольер стал единой ячейкой, в которой оказались все котята.

Для каждого дня, Ася помнит номера котят $$$x_i$$$ и $$$y_i$$$, которые хотели играть вместе, однако она не помнит как котята были поселены в ячейки изначально. Помогите ей найти какое-нибудь возможное начальное расселение котят по $$$n$$$ ячейкам.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 150\,000$$$) — количество котят.

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

Гарантируется, что котята $$$x_i$$$ и $$$y_i$$$ ещё не находились в одной ячейке по итогам предыдущих объединений.

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

Для каждой ячейки от $$$1$$$ до $$$n$$$ выведите целое число — номер котёнка от $$$1$$$ до $$$n$$$, который в ней находился изначально.

Все выведенные числа должны быть различны.

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

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

В ответе к примеру приведено одно из нескольких возможных изначальных расселений котят.

На картинке ниже показано, как происходило объединение ячеек при таком изначальном расселении. Обратите внимание, что котята, желавшие играть вместе в каждый из дней, действительно находились в соседних ячейках.