题目描述

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

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

• 对于所有满足 $1 \\leq x < y \\leq N$ 的整数对 $(x,y)$，
  • 如果 $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$ 是满足题目中条件的有根树。假设在 $R$ 中，顶点 $i$ 的父亲顶点是顶点 $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