题目描述

给定一棵 $n$ 个点的树（$n-1$ 条无向边），节点编号为 $1\sim n$，每条边通过需要 $1$ 单位时间。

此外存在 特殊传送：

• 对任意节点 $i \in [2,n]$，可以 瞬间传送到节点 $1$，耗时 $0$。
• 这种传送在整个过程中最多只能使用一次。

初始在节点 $1$。访问一个节点只需要到达该节点即可，不需要额外时间。

对于所有 $k \in [1,n]$：

• 需要 恰好访问 $k$ 个不同节点
• 最终 必须回到节点 $1$

求最少需要的时间。

输入格式

第一行，一个整数 $n$。

接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$ 表示树的一条边。

输出格式

共 $n$ 行，第 $i$ 行一个整数表示 $k = i$ 的答案。

5
1 2
1 3
2 4
2 5

0
1
2
4
6

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

0
1
2
3
5
7
9
11
13
15

20
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
7 13
7 14
8 15
9 16
9 17
10 18
10 19
14 20

0
1
2
3
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34

提示

样例 1 解释

• $k = 2$ 时，路径可以是 $1 \rightarrow 2 \Rightarrow 1$。
• $k = 3$ 时，路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。
• $k = 4$ 时，路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 3\rightarrow 1$。
• $k = 5$ 时，路径可以是 $1 \rightarrow 3\rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。

数据规模与约定

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq u_i, v_i \leq n$。