Monopolis 是一个美丽而富有的国家。其令人瞩目的特征之一是该国的布局，其中 $N$ 个城市通过 $N - 1$ 条等长的道路相互连接，使得任意两个城市之间都可以通行。

Monopolis 的另一个独特之处在于，每个城市都只有一家银行，且每家银行的资金量都不同。因此，可以给每个城市分配一个介于 $1$ 到 $N$ 之间的不同数字，代表其相对于其他城市的财富排名，其中城市 $1$ 的资金最少，城市 $N$ 的资金最多。

Rob 正在计划去 Monopolis 进行一次“商务旅行”。事实上，Rob 的业务是抢劫。更准确地说，是抢劫银行。Rob 是一个有野心的劫匪，并遵循一种特定的作案手法：他只针对资金比他刚刚抢劫的银行更多的银行。因此，在抢劫了城市 $i$ 之后，他会移动到距离最近的、且资金更多的城市。如果存在多个与城市 $i$ 距离相同且资金更多的城市，他会选择其中资金最少的那一个。如果没有比城市 $i$ 更富有的城市，他就会留在原城市并反思自己的行为。

尽管 Rob 非常坚持自己的作案手法，但他仍在规划他的 Monopolis 之旅，并请求你的帮助。Rob 想知道，对于每个城市 $i$，如果他的第一次抢劫发生在城市 $i$，那么他下一步会访问哪一个城市。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示 Monopolis 的城市数量。每个城市由 $1$ 到 $N$ 之间的一个独特整数标识，按财富递增的顺序排列。

接下来的 $N - 1$ 行，每行包含两个整数 $U$ 和 $V$ ($1 \le U, V \le N$ 且 $U \neq V$)，表示城市 $U$ 和 $V$ 之间有一条双向道路。保证通过给定的道路，任意两个城市之间都存在一条路径。

输出格式

输出单行，包含 $N$ 个整数，其中第 $i$ 个整数表示如果 Rob 的第一次抢劫发生在城市 $i$，他下一步将访问的城市。

样例

输入样例 1

6
1 6
2 5
4 5
3 5
5 6

输出样例 1

6 5 5 5 6 6

输入样例 2

5
5 1
1 3
3 2
2 4

输出样例 2

3 3 4 5 5

输入样例 3

1

输出样例 3

1