配点 : $900$ 点

問題文

高橋くんには $(1,2,...,n)$ の順列 $(p_1,p_2,...,p_n)$ を使い、 次の手順で木を作る能力があります。

頂点 $1$、頂点 $2$、 $...$、 頂点 $n$ を用意する。 各 $i=1,2,...,n$ について次の操作を行う。

• $p_i = 1$ である場合、何もしない。
• $p_i \neq 1$ である場合、$p_j < p_i$ であるような $j$ のうち最大のものを $j'$ とする。 頂点 $i$ と 頂点 $j'$ の間に辺を貼る。

高橋くんはこの能力を使ってお気に入りの木を作ろうとしています。 高橋くんのお気に入りの木は 頂点 $1$ から頂点 $n$ の $n$ 頂点からなり、 $i$ 番目の辺は頂点 $v_i$ と $w_i$ を結んでいます。 適切な順列を使うことで、高橋くんのお気に入りの木と同型な木を作ることが可能か 判定して下さい。 可能な場合、そのような順列のうち辞書順で最も小さいものを求めて下さい。

注意

木が同型であることの定義はwikipedia

を参照して下さい。 直感的には、木と木が同型であるとは、頂点の番号を無視すると同じ木になることを言います。

制約

• $2 \leq n \leq 10^5$
• $1 \leq v_i, w_i \leq n$
• 与えられるグラフは木である

入力

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

$n$

$v_1$ $w_1$

$v_2$ $w_2$

$:$

$v_{n-1}$ $w_{n-1}$

出力

高橋くんのお気に入りの木と同型な木を作ることのできる順列が存在しない場合は -1 を出力せよ。 存在する場合は、辞書順で最小の順列を空白区切りで出力せよ。

6
1 2
1 3
1 4
1 5
5 6

1 2 4 5 3 6

$(1, 2, 4, 5, 3, 6)$ という順列を使って木を作ると、次の図のようになります。

これは入力のグラフと同型です。

6
1 2
2 3
3 4
1 5
5 6

1 2 3 4 5 6

15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

-1