平衡树

题目描述

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

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

1. 对于所有满足 $1 \leq x \lt y \leq N$ 的整数对 $(x,y)$,以下成立: 如果 $R$ 中顶点 $x$ 和 $y$ 的最低公共祖先(最近公共祖先)是顶点 $z$,那么在 $T$ 中,顶点 $z$ 位于顶点 $x$ 和 $y$ 之间的简单路径上。
2. 在 $R$ 中,对于除根以外的所有顶点 $v$,以 $v$ 为根的子树中顶点数的 2 倍,不超过以 $v$ 的父节点为根的子树中顶点数。

可以证明,这样的有根树一定存在。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出格式

设 $R$ 为满足题目描述中条件的有根树。设 $R$ 中顶点 $i$ 的父节点为顶点 $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 倍不超过以顶点 $2$ 为根的子树(有 4 个顶点)的顶点数。

5
1 2
1 3
1 4
1 5

-1 1 1 1 1

数据范围

• $1 \leq N \leq 10^5$
• $1\leq A_i,B_i \leq N$
• 输入中的所有值均为整数。
• 给定的图是一棵树。

提示

答案不唯一，输出任意合法解即可。