题目描述

高桥君有一种能力，可以使用 $(1,2,\ldots,n)$ 的一个排列 $(p_1,p_2,\ldots,p_n)$，按照以下步骤构造一棵树。

准备顶点 $1$、顶点 $2$、$\ldots$、顶点 $n$。对于每个 $i=1,2,\ldots,n$，进行如下操作：

• 如果 $p_i = 1$，则什么也不做。
• 如果 $p_i \neq 1$，则在所有满足 $p_j < p_i$ 的 $j$ 中，取最大的 $j$，记为 $j'$。在顶点 $i$ 和顶点 $j'$ 之间连一条边。

高桥君想用这种能力构造出他最喜欢的树。他最喜欢的树有 $n$ 个顶点，顶点编号为 $1$ 到 $n$，第 $i$ 条边连接顶点 $v_i$ 和 $w_i$。请判断是否存在一个合适的排列，使得高桥君构造出的树与他最喜欢的树同构。如果存在，请输出字典序最小的这样的排列。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

如果不存在能够构造出与高桥君最喜欢的树同构的排列，则输出 -1。
如果存在，输出字典序最小的排列，空格分隔。

样例 1

输入

6
1 2
1 3
1 4
1 5
5 6

输出

1 2 4 5 3 6

样例 2

输入

6
1 2
2 3
3 4
1 5
5 6

输出

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

输出

-1

说明/提示

注意

关于树同构的定义，请参考 wikipedia。直观地说，两棵树同构是指忽略顶点编号后，两棵树的结构完全相同。

约束条件

• $2 \leq n \leq 10^5$
• $1 \leq v_i, w_i \leq n$
• 给定的图一定是一棵树

样例解释 1

使用排列 $(1,\ 2,\ 4,\ 5,\ 3,\ 6)$ 构造出的树如下图所示。

这棵树与输入的图同构。

由 ChatGPT 4.1 翻译