Asya非常喜欢动物。最近,她购买了$$$n$$$小猫,从$$$1$$$和$$$n$$$中数出它们,然后将它们放入笼子里。笼子由一排 $$$n$$$ 单元格组成,从左到右用从 $$$1$$$ 到 $$$n$$$ 的整数进行枚举。相邻的单元格之间有一个部分透明的隔墙,因此最初有 $$$n - 1$$$ 个分区。最初,每个单元格中恰好包含一只具有一定数量的小猫。
通过观察这些小猫,Asya 发现它们非常友好,经常有一对住在相邻牢房的小猫想一起玩耍。于是阿西亚开始拆除相邻牢房之间的隔断。特别是,在$$$i$$$这一天,Asya:
- 注意到,位于相邻单元格的小猫 $$$x_i$$$ 和 $$$y_i$$$ 想要一起玩耍。
- 移除了这两个单元之间的分隔,有效地创建了一个单元,其中包含两个原始单元中的所有小猫。
由于 Asya 从未将隔板放回原处,$$$n - 1$$$ 天后,笼子里只有一个牢房,里面全是小猫。
Asya 每天都会记得想要一起玩耍的小猫 $$$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$$$ 的小猫的索引,它最初是在其中。
所有打印的整数必须不同。
可以保证,至少有一个可能的答案。如果有多个可能的答案,请打印其中任何一个。
示例
输入 #1
5 1 4 2 5 3 1 4 5
输出 #1
3 1 4 2 5
注意
该示例的答案包含小猫的几种可能的初始排列之一。
下图显示了细胞如何在初始排列中联合起来。请注意,每天想要一起玩耍的小猫确实位于相邻的牢房中。