问题陈述

我们有一个编号为$1$到$N$的树$T$。 $T$的第$i$条边连接顶点$u_i$和顶点$v_i$。

让我们使用$T$来定义排列$P = (P_1,P_2,\\ldots,P_N)$（$(1,2,\\ldots,N)$的一种排列）的相似性，具体如下。

• 对于树$T$中的一条简单路径$x=(x_1,x_2,\\ldots,x_k)$，设$y=(P_{x_1}, P_{x_2},\\ldots,P_{x_k})$。相似性是$x$和$y$的最长公共子序列的最大可能长度。

构造一个相似性最小的排列$P$。

什么是子序列？序列的子序列是从该序列中删除零个或多个元素并连接剩余元素而不改变相对顺序得到的序列。例如，$(10,30)$是$(10,20,30)$的一个子序列，但$(20,10)$不是。什么是简单路径？对于图$G$中的顶点$X$和$Y$，从$X$到$Y$的一条路径是一个顶点序列$v_1,v_2, \\ldots, v_k$，满足$v_1=X$，$v_k=Y$，且$v_i$和$v_{i+1}$之间有一条边相连。一个简单路径（或者说是路径）是这样一条路径，其中$v_1,v_2, \\ldots, v_k$各不相同。

约束条件

• $2 \\leq N \\leq 5000$
• $1\\leq u_i,v_i\\leq N$
• 给定的图是一棵树。
• 输入中的所有数都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\\vdots$ $u_{N-1}$ $v_{N-1}$

输出

按照空格分隔打印一个相似性最小的排列$P$。如果存在多个解，则可以打印任意一个。

示例输入1

3
1 2
2 3

示例输出1

3 2 1

该排列的相似性为$1$，可以按照以下方式计算：

• 对于$x=(1)$，我们有$y=(P_1)=(3)$。 $x$和$y$的最长公共子序列的长度为$0$。

• 对于$x=(2)$，我们有$y=(P_2)=(2)$。 $x$和$y$的最长公共子序列的长度为$1$。

• 对于$x=(3)$，我们有$y=(P_2)=(1)$。 $x$和$y$的最长公共子序列的长度为$0$。

• 对于$x=(1,2)$，我们有$y=(P_1,P_2)=(3,2)$。 $x$和$y$的最长公共子序列的长度为$1$。 对于$(1,2)$的逆序$(2,1)$同样如此。

• 对于$x=(2,3)$，我们有$y=(P_2,P_3)=(2,1)$。 $x$和$y$的最长公共子序列的长度为$1$。 对于$(2,3)$的逆序$(3,2)$同样如此。

• 对于$x=(1,2,3)$，我们有$y=(P_1,P_2,P_3)=(3,2,1)$。 $x$和$y$的最长公共子序列的长度为$1$。 对于$(1,2,3)$的逆序$(3,2,1)$同样如此。

我们可以证明没有排列具有相似性为$0$或更小的，因此这个排列是一个有效的答案。

示例输入2

4
2 1
2 3
2 4

示例输出2

3 4 1 2

如果有多个排列具有最小的相似性，您可以打印其中任何一个。例如，也可以打印4 3 2 1。