题目描述

高桥君的公司有 $N$ 个房间，每个房间编号为 $1$ 到 $N$。此外，有 $N-1$ 条通道，第 $i$ 条通道连接房间 $a_i$ 和房间 $b_i$。已知任意两个房间之间都可以仅通过这些通道互相到达。

现在高桥君迷路到了某个房间，这个房间记作 $r$。他决定采用如下方法反复移动，直到回到自己的房间（房间 $1$）：

• 在所有与已访问过的房间相邻且尚未访问过的房间中，选择编号最小的房间移动过去。

设高桥君从房间 $r$ 回到房间 $1$ 需要移动的次数为 $c_r$。请你求出 $c_2, c_3, ..., c_N$ 的值。

注意：无论一次移动经过多少条通道，都只计为一次移动。

输入格式

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

$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

输出

5 5 5 1 5

样例 2

输入

6
1 2
2 3
3 4
4 5
5 6

输出

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

输出

7 5 3 1 3 4 7 4 5

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• 输入给出的图是一棵树。

样例解释 1

例如，如果高桥君迷路到了房间 $2$，他会按如下顺序移动：

• 移动到房间 $6$。
• 移动到房间 $3$。
• 移动到房间 $4$。
• 移动到房间 $5$。
• 移动到房间 $1$。

由 ChatGPT 4.1 翻译