問題文

頂点に $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$ への 単純パス (あるいは単に パス) と呼びます。

制約

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

入力例 2

4
2 1
2 3
2 4

出力例 2

3 4 1 2

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