配点 : $600$ 点

問題文

頂点に $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$ を一つ構築してください。

制約

• $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$ を空白区切りで出力せよ。解が複数存在する場合、どれを出力しても正解とみなされる。

3
1 2
2 3

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_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$ 以下の順列は存在しないことが証明できるので、これが答えとなります。

4
2 1
2 3
2 4

3 4 1 2

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