Problem
Asya 非常喜欢动物。她最近买了 n 只小猫，给它们从 1 到 n 的数字标识符，并将它们放在一个围栏里。鸟舍是一排 n 个单元格，也从 1 到 n 编号。相邻的单元格由网格隔板分隔，外壳中总共有 n & minus; 1 个隔板。最初，每个牢房中只有一只小猫和一定数量的小猫。
看着小猫，Asya 注意到它们非常友好，住在相邻牢房中的几对小猫真的很想互相玩耍。为了不剥夺他们的这种乐趣，阿西娅开始拆掉相邻牢房之间的隔板，让它们变得更大。
在第 i 天，Asya 做了以下事情。
我注意到一些小猫 x
i 和 y
i，在第 i 天住在相邻的牢房里，想玩。
我移除了这些牢房之间的隔板，将它们合二为一，前两个牢房的所有小猫都在里面。
由于 Asya 没有归还隔板，n & minus; 1 天后，围栏变成了所有小猫居住的单间。非常迂腐的阿西娅在一本特别的日记本上记下了每天 n−1 天的小猫 ID x
i 和 y
i
你有一本包含这些信息的杂志，但你不知道小猫最初是如何在牢房里安顿下来的。在 n 个原始单元格中找到与日志中的数据不矛盾的任何小猫分布。
输入
第一行包含一个整数 n (
\(2 \leq n \leq 150000\)) —小猫的数量。
接下来的 n−1 行包含整数对 x
i , y
i (
\(1 \leq x_i , y_i, \leq n,x_i \neq y_i\) ) —小猫的标识符，在第 i 天移除分区的单元格之间。确保小猫 xi 和 yi 不会因为之前的单元格合并而在同一个单元格中。
印记
打印 n 个不同的整数 p
i (
\(1 \leq p_i \leq n\))，其中 p
i ——最初住在单元格 i 中的小猫的标识符。如果有几个可能的答案，打印其中的任何一个。
注意
例如，答案中给出了小猫可能的初始定居点之一，还有其他答案。下图显示了如何为小猫的初始放置合并单元格。请注意，在这种安排下，根据 Asya 的日志，每天成为朋友的小猫都在相邻的牢房中。
<正文>
| 输入 |
输出 |
5
14
25
3 1
4 5 |
3 1 4 2 5 |