Ася очень любит животных. Недавно она приобрела \(n\) котят, пронумеровала их от \(1\) до \(n\) и поселила в вольере. Вольер представляет собой ряд из \(n\) ячеек, пронумерованных от \(1\) до \(n\) слева направо. Cоседние ячейки разделены сетчатыми перегородками, всего в вольере \(n - 1\) перегородок. Изначально в каждой ячейке поселился ровно один котёнок с некоторым номером.
Наблюдая за котятами, Ася заметила, что они очень дружелюбны и некоторые пары живущих в соседних ячейках котят очень хотят играть друг с другом. Чтобы не лишать их этого удовольствия, Ася стала вынимать перегородки между соседними ячейками. В частности, в \(i\)-й день, Ася:
- Обратила внимание, что котята \(x_i\) и \(y_i\), живущие в соседних ячейках, хотят играть вместе.
- Удаляла перегородку между этими ячейками, превращая их в одну, в которой оказывались все котята из двух прежних ячеек.
Поскольку Ася ни разу возвращала перегородки, через \(n - 1\) день вольер стал единой ячейкой, в которой оказались все котята.
Для каждого дня, Ася помнит номера котят \(x_i\) и \(y_i\), которые хотели играть вместе, однако она не помнит как котята были поселены в ячейки изначально. Помогите ей найти какое-нибудь возможное начальное расселение котят по \(n\) ячейкам.
Выходные данные
Для каждой ячейки от \(1\) до \(n\) выведите целое число — номер котёнка от \(1\) до \(n\), который в ней находился изначально.
Все выведенные числа должны быть различны.
Гарантируется, что существует хотя бы один возможный ответ. В случае, если существует несколько решений, выведите любое из них.
Примечание
В ответе к примеру приведено одно из нескольких возможных изначальных расселений котят.
На картинке ниже показано, как происходило объединение ячеек при таком изначальном расселении. Обратите внимание, что котята, желавшие играть вместе в каждый из дней, действительно находились в соседних ячейках.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4
2 5
3 1
4 5
|
3 1 4 2 5
|