CF1131F.Asya And Kittens

Asya loves animals very much. Recently, she purchased $n$ kittens, enumerated them from $1$ and $n$ and then put them into the cage. The cage consists of one row of $n$ cells, enumerated with integers from $1$ to $n$ from left to right. Adjacent cells had a partially transparent partition wall between them, hence there were $n - 1$ partitions originally. Initially, each cell contained exactly one kitten with some number.

Observing the kittens, Asya noticed, that they are very friendly and often a pair of kittens in neighboring cells wants to play together. So Asya started to remove partitions between neighboring cells. In particular, on the day $i$, Asya:

• Noticed, that the kittens $x_i$ and $y_i$, located in neighboring cells want to play together.
• Removed the partition between these two cells, efficiently creating a single cell, having all kittens from two original cells.

Since Asya has never putted partitions back, after $n - 1$ days the cage contained a single cell, having all kittens.

For every day, Asya remembers numbers of kittens $x_i$ and $y_i$, who wanted to play together, however she doesn't remember how she placed kittens in the cage in the beginning. Please help her and find any possible initial arrangement of the kittens into $n$ cells.

阿西娅非常喜爱小动物。最近，她购买了 $n$ 只小猫，将它们编号为 $1$ 到 $n$，然后放入笼子中。笼子由一行 $n$ 个单元格组成，从左到右依次编号为 $1$ 到 $n$。相邻单元格之间原本有一堵半透明的隔板，因此最初共有 $n - 1$ 块隔板。初始时，每个单元格中恰好有一只编号为某个整数的小猫。

在观察小猫的过程中，阿西娅注意到它们非常友善，常常有两只位于相邻单元格中的小猫想要一起玩耍。于是，阿西娅开始移除相邻单元格之间的隔板。具体来说，在第 $i$ 天，阿西娅：

• 发现位于相邻单元格中的小猫 $x_i$ 和 $y_i$ 想要一起玩耍；
• 移除了这两个单元格之间的隔板，从而有效地将这两个原始单元格合并为一个新单元格，其中包含原来两个单元格中的所有小猫。

由于阿西娅从未重新安装过任何隔板，因此经过 $n - 1$ 天后，笼子中只剩下一个单元格，其中包含了全部 $n$ 只小猫。

对于每一天，阿西娅都记得想一起玩耍的小猫编号 $x_i$ 和 $y_i$，但她不记得最开始是如何将小猫放入 $n$ 个单元格中的。请帮助她找出任意一种可能的初始安排方式（即小猫在 $n$ 个单元格中的初始排列）。

The first line contains a single integer $n$ ($2 \le n \le 150\,000$) — the number of kittens.

Each of the following $n - 1$ lines contains integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$) — indices of kittens, which got together due to the border removal on the corresponding day.

It's guaranteed, that the kittens $x_i$ and $y_i$ were in the different cells before this day.

第一行包含一个整数 $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$ 位于不同的单元格中。

For every cell from $1$ to $n$ print a single integer — the index of the kitten from $1$ to $n$, who was originally in it.

All printed integers must be distinct.

It's guaranteed, that there is at least one answer possible. In case there are multiple possible answers, print any of them.

对于从 $1$ 到 $n$ 的每个格子，输出一个整数——即最初位于该格子中的小猫的编号（编号范围为 $1$ 到 $n$）。

所有输出的整数必须互不相同。

题目保证至少存在一种可行解。若存在多种可行解，输出任意一种即可。

The answer for the example contains one of several possible initial arrangements of the kittens.

The picture below shows how the cells were united for this initial arrangement. Note, that the kittens who wanted to play together on each day were indeed in adjacent cells.

示例的答案包含小猫的若干种可能初始排列之一。

下图展示了针对该初始排列，各单元格是如何合并的。注意，每天想要一起玩耍的小猫确实位于相邻的单元格中。