分数: 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