← 返回题目列表

AtCoder · arc095_d

F. 排列树

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

高桥有能力使用排列生成树 (p_1,p_2,...,p_n) of (1,2,...,n),在以下过程中:

首先,准备Vertex 1,顶点 2, ..., 顶点 N。 对于每个 i=1,2,...,n,执行以下操作:

  • If p_i = 1,什么都不做。
  • If p_i \neq 1,让 j' 成为最大的 j 这样 p_j < p_i.跨越顶点之间的边 i 和顶点 j'.

高桥正试图用这种能力制作他最喜欢的树。 他最喜欢的树有 n 来自顶点的顶点 1 通过顶点 n,及其 i第一条边连接顶点 v_i 和 w_i。 确定他是否可以通过使用适当的排列使一棵树与他最喜欢的树同构。 如果他能做到,找到字典顺序最小的这种排列。

注释

树同构的定义参见 维基百科。直观上,如果我们忽略它们顶点的索引,当两棵树“相同”时,它们是同构的。

约束

  • 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