题目描述

高橋くんには $(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$ を結んでいます。 適切な順列を使うことで、高橋くんのお気に入りの木と同型な木を作ることが可能か 判定して下さい。 可能な場合、そのような順列のうち辞書順で最も小さいものを求めて下さい。

输入格式

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

$n$ $v_1$ $w_1$ $v_2$ $w_2$ $:$ $v_{n-1}$ $w_{n-1}$

输出格式

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

题目大意

给定一棵树 $\rm T$, 要求构造一个排列 $p$ .

对于每一个 $p_i$ ，找到最大的 $j$ 使得 $p_j<p_i$，然后在 $i,j$ 间连边。

问是否可以构造出与 $\rm T$ 同构的树。

如果可以，则给出字典序最小的排列。

$n\leq 100,000$

6
1 2
1 3
1 4
1 5
5 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

提示

注意

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

制約

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

Sample Explanation 1

$(1,\ 2,\ 4,\ 5,\ 3,\ 6)$ という順列を使って木を作ると、次の図のようになります。  これは入力のグラフと同型です。