题目描述

Asya 很喜欢动物。她最近买了 $n$ 只小猫，编号为 $1$ 到 $n$，并把它们分别放入一排 $n$ 个笼格中。笼格从左到右编号为 $1$ 到 $n$，相邻笼格之间有半透明隔板；最初每个笼格恰好放一只小猫。

小猫们非常友好。连续 $n-1$ 天中，每天都有两只分别处在相邻连续区域里的小猫想一起玩。第 $i$ 天，Asya 记下这两只小猫的编号 $x_i,y_i$，然后拆掉它们所在区域之间的那块隔板，使两个区域合并成一个更大的连续区域。已经拆掉的隔板不会重新装回，因此在第 $n-1$ 天结束后，全部小猫位于同一个大笼格中。

Asya 还记得每天的 $x_i,y_i$，却忘记了最初每个笼格中放的是哪只小猫。请构造一种可能的初始排列，使每天记录的两只小猫在当天确实位于两个相邻区域中，能够通过拆除它们之间的隔板完成合并。

输入格式

第一行包含整数 $n$，表示小猫数量。

接下来 $n-1$ 行，每行包含两个不同的整数 $x_i,y_i$，表示第 $i$ 天促使 Asya 拆除隔板的两只小猫。

输入保证在第 $i$ 天开始前，$x_i$ 与 $y_i$ 位于两个不同区域中，并且至少存在一种符合全部记录的初始排列。

输出格式

输出 $n$ 个互不相同的整数，依次表示最初从左到右各笼格中的小猫编号。若有多种可行排列，输出任意一种。

5
1 4
2 5
3 1
4 5

3 1 4 2 5

样例说明 #1

一种合法排列是 3 1 4 2 5，每天给出的两个小猫所在块都在当时相邻。

2
1 2

1 2

样例说明 #2

只有两只小猫，任意将它们相邻排列都能完成唯一一次合并。

4
1 2
3 4
2 3

1 2 3 4

样例说明 #3

先分别形成两个连续块，最后通过小猫 $2,3$ 所在的边界把两块连接。

数据范围与约定

$2\le n\le 150000$，$1\le x_i,y_i\le n$，且 $x_i\ne y_i$。每次记录中的两只小猫在合并前属于不同区域。