当前没有测试数据。

平衡树

分数：$600$ 分

问题描述

给定一个有 $N$ 个顶点的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

构造一个满足以下条件的 $N$ 个顶点的有根树 $R$。

• 对于所有整数对 $(x,y)$ 满足 $1 \leq x < y \leq N$，
  • 如果 $R$ 中顶点 $x$ 和 $y$ 的最低公共祖先是顶点 $z$，则 $T$ 中的顶点 $z$ 在顶点 $x$ 和 $y$ 的简单路径上。
• 在 $R$ 中，对于除根以外的所有顶点 $v$，以 $v$ 为根的子树的顶点数乘以 $2$ 不超过父节点为根的子树的顶点数。

我们可以证明这样的有根树始终存在。

约束条件

• $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$ 在 $R$ 中的父节点是顶点 $p_i$。（如果 $i$ 是根节点，则令 $p_i=-1$。）
打印 $N$ 个整数 $p_1,\ldots,p_N$，以空格分隔。

4
1 2
2 3
3 4

2 -1 4 2

例如，$R$ 中顶点 $1$ 和 $3$ 的最低公共祖先是顶点 $2$；在 $T$ 中，顶点 $2$ 在顶点 $1$ 和 $3$ 的简单路径上。
又例如，在 $R$ 中，以顶点 $4$ 为根的子树有两个顶点，并且乘以 $2$ 后的数量不超过以顶点 $2$ 为根的子树的顶点数，该子树有 $4$ 个顶点。

5
1 2
1 3
1 4
1 5

-1 1 1 1 1