{"raw_statement":[{"iden":"background","content":"——『太阳』这种东西，以前似乎是存在的。\n\n传说是这么讲的——白色的火焰发出闪耀的光芒，天空则是清澄无比的蔚蓝。\n\n据说诸神与其创造物所掀起的『大战』，使得大地化为焦土，灰烬遮蔽了苍穹。\n\n灰烬冲击到天上流动的星辰之力——精灵回廊，发出了光芒，将天空染成红色。\n\n而那样的红色，覆盖了仍然持续着互相残杀的每一块土地。\n\n或者那是这个星球本身发出的悲鸣与流出的鲜血吧……\n\n血色的天空上，只有——蓝色的灰飘然落下。\n\n~~回来吧3579，我最骄傲的信仰/ll~~"},{"iden":"statement","content":"里克在视线可及的范围内发现了一颗古老的「神树」。\n\n神树是一颗树，树上有 $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\n此外，有 $n - 1$ 条特殊连接，对于每个魔法装置 $i \\in [2, n]$，可以**瞬间**传送到第 $1$ 个魔法装置，花费 $0$ 单位时间。**特殊连接总共只能使用一次**。\n\n里克初始在魔法装置 $1$ 处。现在，给出这棵「神树」的结构，里克想要在若干时间内研究尽可能多的魔法装置。我们假定，研究一个魔法装置只需要到达该装置处，并且不需要花费额外时间。\n\n里克想让你尽快计算出，对所有 $k \\in [1, n]$，如果要恰好研究 $k$ 个不同的魔法装置，**并且随之返回魔法装置 $\\bm 1$**，最少应花费多少时间。"},{"iden":"input","content":"第一行，一个整数 $n$。\n\n接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$。"},{"iden":"output","content":"共 $n$ 行，第 $i$ 行一个整数表示 $k = i$ 的答案。"},{"iden":"note","content":"**【样例解释 $\\bm 1$】**\n\n+ $k = 1$ 时，里克只需要呆在装置 $1$ 处。\n+ $k = 2$ 时，里克的路径可以是 $1 \\rightarrow 2 \\Rightarrow 1$。\n+ $k = 3$ 时，里克的路径可以是 $1 \\rightarrow 2 \\rightarrow 4 \\Rightarrow 1$。\n+ $k = 4$ 时，里克的路径可以是 $1 \\rightarrow 2 \\rightarrow 4 \\Rightarrow 1 \\rightarrow 3\\rightarrow 1$。\n+ $k = 5$ 时，里克的路径可以是 $1 \\rightarrow 3\\rightarrow 1 \\rightarrow 2 \\rightarrow 5 \\rightarrow 2 \\rightarrow 4 \\Rightarrow 1$。\n\n**【样例解释 $\\bm 2$】**\n\n这组数据满足测试点编号 $13 \\sim 20$ 的性质。\n\n**【数据规模与约定】**\n\n| 测试点编号 | 特殊限制 |\n| :--------: | :------: |\n| $1 \\sim 2$ | $n = 3$ |\n| $3 \\sim 4$ | $n = 5$ |\n| $5 \\sim 6$ | $n = 100$ |\n| $7 \\sim 8$ | $n = 1000$ |\n| $9 \\sim 10$ | $u_i = 1, v_i = i + 1$ |\n| $11 \\sim 12$ | $u_i = i, v_i = i + 1$ |\n| $13 \\sim 20$ | 无特殊限制 |\n\n对于所有数据，$1 \\leq n \\leq 10^5$，$1 \\leq u_i, v_i \\leq n$。"}],"translated_statement":null,"sample_group":[["5\n1 2\n1 3\n2 4\n2 5","0\n1\n2\n4\n6"],["见下发的 hope/hope2.in","见下发的 hope/hope2.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}