F - Permutation Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 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 を出力せよ。 存在する場合は、辞書順で最小の順列を空白区切りで出力せよ。

入力例 1

6
1 2
1 3
1 4
1 5
5 6

出力例 1

1 2 4 5 3 6

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

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

入力例 2

6
1 2
2 3
3 4
1 5
5 6

出力例 2

1 2 3 4 5 6

入力例 3

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

出力例 3

-1

Score : 900 points

Problem Statement

Takahashi has an ability to generate a tree using a permutation (p_1,p_2,...,p_n) of (1,2,...,n), in the following process:

First, prepare Vertex 1, Vertex 2, ..., Vertex N. For each i=1,2,...,n, perform the following operation:

  • If p_i = 1, do nothing.
  • If p_i \neq 1, let j' be the largest j such that p_j < p_i. Span an edge between Vertex i and Vertex j'.

Takahashi is trying to make his favorite tree with this ability. His favorite tree has n vertices from Vertex 1 through Vertex n, and its i-th edge connects Vertex v_i and w_i. Determine if he can make a tree isomorphic to his favorite tree by using a proper permutation. If he can do so, find the lexicographically smallest such permutation.

Notes

For the definition of isomorphism of trees, see wikipedia. Intuitively, two trees are isomorphic when they are the "same" if we disregard the indices of their vertices.

Constraints

  • 2 \leq n \leq 10^5
  • 1 \leq v_i, w_i \leq n
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

If there is no permutation that can generate a tree isomorphic to Takahashi's favorite tree, print -1. If it exists, print the lexicographically smallest such permutation, with spaces in between.

Sample Input 1

6
1 2
1 3
1 4
1 5
5 6

Sample Output 1

1 2 4 5 3 6

If the permutation (1, 2, 4, 5, 3, 6) is used to generate a tree, it looks as follows:

This is isomorphic to the given graph.

Sample Input 2

6
1 2
2 3
3 4
1 5
5 6

Sample Output 2

1 2 3 4 5 6

Sample Input 3

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

Sample Output 3

-1