题目描述

頂点に $1$ から $N$ の番号がついた木 $T$ があります。 $T$ の $i\ (1\leq\ i\ \leq\ N-1)$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。

$T$ を用いて、$(1,2,\ldots,N)$ の順列 $P\ =\ (P_1,P_2,\ldots,P_N)$ の類似度を以下で定めます。

• $T$ 上の任意の単純パス $x=(x_1,x_2,\ldots,x_k)$ に対して、$y=(P_{x_1},\ P_{x_2},\ldots,P_{x_k})$ とする。このとき、$x$ と $y$ の最長共通部分列の長さとして考えられる最大値を類似度とする。

類似度が最小となるような順列 $P$ を一つ構築してください。

部分列とは 数列の部分列とは、数列から $0$ 個以上の要素を取り除いた後、残りの要素を元の順序で連結して得られる数列のことをいいます。 例えば、$(10,30)$ は $(10,20,30)$ の部分列ですが、$(20,10)$ は $(10,20,30)$ の部分列ではありません。 単純パスとは グラフ $G$ 上の頂点 $X,Y$ に対して、頂点列 $v_1,v_2,\ \ldots,\ v_k$ であって、 $v_1=X$, $v_k=Y$ かつ、$1\leq\ i\leq\ k-1$ に対して $v_i$ と $v_{i+1}$ が辺で結ばれているようなものを頂点 $X$ から頂点 $Y$ への ウォーク と呼びます。 さらに、$v_1,v_2,\ \ldots,\ v_k$ がすべて異なるようなものを頂点 $X$ から頂点 $Y$ への 単純パス (あるいは単に パス) と呼びます。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

類似度が最小となるような順列 $P$ を空白区切りで出力せよ。解が複数存在する場合、どれを出力しても正解とみなされる。

题目大意

给定一棵 $n$ 个节点的树 $T$ 。

我们以下面的方式定义一个长度为 $n$ 的排列 $P$ 的价值：

考虑一条树 $T$ 上的简单路径 $x=(x_1,x_2,\dots ,x_k)$，我们令 $y=(p_{x_1},p_{x_2},\dots,p_{x_k})$，这条路径的价值就是序列 $x$ 和序列 $y$ 的最长公共子序列的长度。排列 $P$ 的价值树上所有的简单路径的权值的最大值。

你需要构造一个排列 $P$，使得 $P$ 与树 $T$ 的相似度最小。

3
1 2
2 3

3 2 1

4
2 1
2 3
2 4

3 4 1 2

提示

制約

• $2\ \leq\ N\ \leq\ 5000$
• $1\leq\ u_i,v_i\leq\ N$
• 与えられるグラフは木
• 入力される数値は全て整数

Sample Explanation 1

出力例の順列の類似度は $1$ となっています。これは、以下のように計算できます。 - $x=(1)$ のとき $y=(P_1)=(3)$ です。$x,y$ の最長共通部分列の長さは $0$ です。 - $x=(2)$ のとき $y=(P_2)=(2)$ です。$x,y$ の最長共通部分列の長さは $1$ です。 - $x=(3)$ のとき $y=(P_3)=(1)$ です。$x,y$ の最長共通部分列の長さは $0$ です。 - $x=(1,2)$ のとき $y=(P_1,P_2)=(3,2)$ です。$x,y$ の最長共通部分列の長さは $1$ です。 これを反転した $x=(2,1)$ についても同様です。 - $x=(2,3)$ のとき $y=(P_2,P_3)=(2,1)$ です。$x,y$ の最長共通部分列の長さは $1$ です。 これを反転した $x=(3,2)$ についても同様です。 - $x\ =\ (1,2,3)$ のとき $y=(P_1,P_2,P_3)=(3,2,\ 1)$ です。$x,y$ の最長共通部分列の長さは $1$ です。これを反転した $x=(3,2,1)$ についても同様です。 類似度が $0$ 以下の順列は存在しないことが証明できるので、これが答えとなります。

Sample Explanation 2

類似度が最小の順列が複数存在する場合、どれを出力してもよいです。例えば、4 3 2 1 といった出力も正解になります。