AT_arc095_d.[ARC095F] Permutation Tree

高桥君有一种能力，可以使用 $ (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。
如果存在，输出字典序最小的排列，空格分隔。

注意

关于树同构的定义，请参考 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 翻译