题目背景

——『太阳』这种东西，以前似乎是存在的。

传说是这么讲的——白色的火焰发出闪耀的光芒，天空则是清澄无比的蔚蓝。

据说诸神与其创造物所掀起的『大战』，使得大地化为焦土，灰烬遮蔽了苍穹。

灰烬冲击到天上流动的星辰之力——精灵回廊，发出了光芒，将天空染成红色。

而那样的红色，覆盖了仍然持续着互相残杀的每一块土地。

或者那是这个星球本身发出的悲鸣与流出的鲜血吧……

血色的天空上，只有——蓝色的灰飘然落下。

回来吧3579，我最骄傲的信仰/ll

题目描述

里克在视线可及的范围内发现了一颗古老的「神树」。

神树是一颗树，树上有 $n$ 个含有魔法装置的位置。经过初步「考察」，有 $n - 1$ 条魔法连接，第 $i(1 \leq i \leq n - 1)$ 条连接连接 $1 \leq u_i \neq v_i \leq n$ 两个魔法装置。这两个装置可以相互双向地在 $1$ 单位时间内通行，保证仅由这 $n - 1$ 条连接，每个魔法装置都可以相互到达。

此外，有 $n - 1$ 条特殊连接，对于每个魔法装置 $i \in [2, n]$，可以瞬间传送到第 $1$ 个魔法装置，花费 $0$ 单位时间。特殊连接总共只能使用一次。

里克初始在魔法装置 $1$ 处。现在，给出这棵「神树」的结构，里克想要在若干时间内研究尽可能多的魔法装置。我们假定，研究一个魔法装置只需要到达该装置处，并且不需要花费额外时间。

里克想让你尽快计算出，对所有 $k \in [1, n]$，如果要恰好研究 $k$ 个不同的魔法装置，并且随之返回魔法装置 $\bm 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

见下发的 hope/hope2.in

见下发的 hope/hope2.ans

提示

【样例解释 $\bm 1$】

• $k = 1$ 时，里克只需要呆在装置 $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$。

【样例解释 $\bm 2$】

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

【数据规模与约定】

测试点编号	特殊限制
$1 \sim 2$	$n = 3$
$3 \sim 4$	$n = 5$
$5 \sim 6$	$n = 100$
$7 \sim 8$	$n = 1000$
$9 \sim 10$	$u_i = 1, v_i = i + 1$
$11 \sim 12$	$u_i = i, v_i = i + 1$
$13 \sim 20$	无特殊限制

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