题目描述

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

神树是一棵树，树上有 $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$ 的答案。

样例 #1

样例输入 #1

5
1 2
1 3
2 4
2 5

样例输出 #1

0
1
2
4
6

提示

样例解释

$k = 1$ 时，里克只需要呆在装置 $1$ 处，花费 $0$。

$k = 2$ 时，里克的路径可以是 $1 \rightarrow 2 \Rightarrow 1$（其中 $\Rightarrow$ 表示使用一次特殊连接瞬间返回），花费 $1$。

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

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

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

数据范围

对于所有数据，保证：

• $1 \leq n \leq 10^5$；
• $1 \leq u_i, v_i \leq n$，且给出的 $n - 1$ 条边构成一棵树（从装置 $1$ 出发可以到达任意装置）。

本题采用捆绑测试，各测试点特殊限制如下：