题目描述

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

高桥迷路在其中一个房间里。设这个房间为$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$

样例输入 1

6
1 5
5 6
6 2
6 3
6 4

样例输出 1

5 5 5 1 5

例如，如果高桥迷路在房间$2$中，他将按照以下步骤旅行：

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

样例输入 2

6
1 2
2 3
3 4
4 5
5 6

样例输出 2

1 2 3 4 5

样例输入 3

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

样例输出 3

7 5 3 1 3 4 7 4 5