题目描述

Takahashi 有一种通过排列 $(p_1,p_2,...,p_n)$ 可以生成一棵树的能力，具体过程如下：

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

• 如果 $p_i = 1$，什么都不做。
• 如果 $p_i \\neq 1$，找到最大的 $j$ 使得 $p_j < p_i$。在顶点 $i$ 和顶点 $j'$ 之间构建一条边。

Takahashi 正在尝试使用这种能力制作他最喜欢的树。他最喜欢的树由 $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}$

输出

如果不存在能够生成与 Takahashi 最喜欢的树同构的排列，则打印 -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