You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

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

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

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

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

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

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

题目描述

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

神树是一颗树，树上有 $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$ 单位时间内通行，保证仅由这 $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 \leq n \leq 10^5$，$1 \leq u_i, v_i \leq n$。