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](https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%90%8C%E5%9E%8B)。直观地说，两棵树同构是指忽略顶点编号后，两棵树的结构完全相同。 ### 约束条件 - $ 2 \leq n \leq 10^5 $ - $ 1 \leq v_i, w_i \leq n $ - 给定的图一定是一棵树 ### 样例解释 1 使用排列 $ (1,\ 2,\ 4,\ 5,\ 3,\ 6) $ 构造出的树如下图所示。  这棵树与输入的图同构。 由 ChatGPT 4.1 翻译