题目描述

LiurK发现了一颗古老的神树。树上有 $n$ 个魔法宝石，他们由$n - 1$ 条双向枝干连接，使得每个魔法宝石都可以相互到达。第 $i(1 \leq i \leq n - 1)$ 条枝干连接 $u_i, v_i$ 两个魔法宝石，保证 $u_i \neq v_i$ 且 $1\leq u_i,v_i\leq n$，这两个宝石可以相互在 $1$ 单位时间内通行。

此外，每个宝石都有一个到1号魔法宝石的单向快速通道，使得它可以花费 $0$ 单位时间快速到达1号魔法宝石。注意一次寻宝过程中只能使用一次通道。

LiurK初始在1号魔法宝石处。他想要在若干时间内找到尽可能多的魔法宝石。

请你帮他计算出，对所有 $k \in [1, n]$，如果要恰好研究 $k$ 个不同的魔法装置，并且随之返回$\bm 1$号宝石位置，最少应花费多少时间。

输入格式

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

接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$。

输出格式

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

输入输出样例 #1

输入 #1

5
1 2
1 3
2 4
2 5

输出 #1

0
1
2
4
6

输入输出样例 #2

输入 #2

见下发的gem2.in

输出 #2

见下发的 gem2.ans

说明/提示

【样例解释 $\bm 1$】

• $k = 1$ 时，LiurK只需要呆在$1$ 处。
• $k = 2$ 时，LiurK的路径可以是 $1 \rightarrow 2 \Rightarrow 1$。
• $k = 3$ 时，LiurK的路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。
• $k = 4$ 时，LiurK的路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 3\rightarrow 1$。
• $k = 5$ 时，LiurK的路径可以是 $1 \rightarrow 3\rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。

【样例解释 $\bm 2$】

这组数据满足测试点编号 $13 \sim 20$ 的性质。

【数据规模与约定】

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