分数 : $1200$ 分

问题陈述

Takahashi 的办公室有 $N$ 个房间。每个房间的 ID 从 $1$ 到 $N$。 还有 $N-1$ 条走廊，第 $i$ 条走廊连接房间 $a_i$ 和房间 $b_i$。 已知可以仅通过这些走廊在任意两个房间之间旅行。

Takahashi 在某个房间迷路了。设这个房间为 $r$。 他决定通过反复以以下方式旅行回到他的房间，即房间 $1$：

• 前往与已访问房间相邻但尚未访问的房间中 ID 最小的房间。

设 $c_r$ 为回到房间 $1$ 所需的旅行次数。 找出所有 $c_2,c_3,...,c_N$。 注意，无论他在一次旅行中经过多少条走廊，仍然只算作一次旅行。

约束条件

• $2 \leq N \leq 2\times 10^5$
• $1 \leq a_i,b_i \leq N$
• $a_i \neq b_i$
• 输入的图是树形结构。

输入

输入通过标准输入以以下格式给出：

$N$

$a_1$ $b_1$

$:$

$a_{N-1}$ $b_{N-1}$

输出

打印每个 $r$ 的 $c_r$，格式如下：

$c_2$ $c_3$ $...$ $c_N$

6
1 5
5 6
6 2
6 3
6 4

5 5 5 1 5

例如，如果 Takahashi 在房间 $2$ 迷路，他将按如下方式旅行：

• 前往房间 $6$。
• 前往房间 $3$。
• 前往房间 $4$。
• 前往房间 $5$。
• 前往房间 $1$。

6
1 2
2 3
3 4
4 5
5 6

1 2 3 4 5

10
1 5
5 6
6 10
6 4
10 3
10 8
8 2
4 7
4 9

7 5 3 1 3 4 7 4 5