分数: 600 点
问题陈述
你得到一棵树 T 与 N 顶点。 的 i第一条边连接顶点 A_i 和 B_i.
构建一个 N- 顶点有根树 R 满足以下条件。
- 对于所有整数对 (x,y) 这样 1 \leq x < y \leq N,
- 如果最低共同祖先在 R 顶点数 x 和 y 是顶点 z,然后顶点 z in T 位于顶点之间的简单路径上 x 和 y.
- In R,对于所有顶点 v 除根外,以子树为根的子树的顶点数 v,乘以 2,不超过以父级为根的子树的顶点数 v.
我们可以证明这样一棵有根的树总是存在的。
约束
- 1 \leq N \leq 10^5
- 1\leq A_i,B_i \leq N
- 输入中的所有值都是整数。
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
输出
让 R 是满足问题陈述中的条件的有根树。 假设顶点的父节点 i in R 是顶点 p_i。 (如果 i 是根,让 p_i=-1.)
打印 N 整数 p_1,\ldots,p_N,中间有空格。
示例输入 1
4 1 2 2 3 3 4
示例输出 1
2 -1 4 2
例如,最低共同祖先 R 顶点数 1 和 3 是顶点 2;在 T,顶点 2 位于顶点之间的简单路径上 1 和 3.
另外,例如,在 R,以顶点为根的子树 4 有两个顶点,且数量乘以2不超过以顶点为根的子树的顶点数 2,其中有 4 顶点。

示例输入 2
5 1 2 1 3 1 4 1 5
示例输出 2
-1 1 1 1 1