有 $N$ 个岛屿，海狸居住在这些岛屿上。岛屿编号为 $1$ 到 $N$。这些岛屿由 $N-1$ 条双向桥梁连接。桥梁编号为 $1$ 到 $N-1$。第 $i$ 条桥连接岛屿 $A_i$ 和岛屿 $B_i$。通过这些桥梁，可以在任意两个岛屿之间往来。每个岛屿上都住着一只海狸。

有时，居住在某些岛屿上的海狸会聚集在一个岛屿上举行会议。当会议的参加者确定后，会选择满足以下条件的岛屿作为会议地点： 参加者聚集到该地点所经过的桥梁数量之和最小。

在这里，当会议的参加者确定后，每位参加者都会通过最少数量的桥梁从其居住的岛屿移动到会议地点。

如果会议地点的候选岛屿很多，参加者们会非常期待这次会议。当会议的参加者确定后，会议的期望得分计算为满足上述条件的候选岛屿的数量。对于 $1$ 到 $N$ 之间的每个整数 $j$，你需要求出有 $j$ 只海狸参加的会议的最大期望得分。

编写一个程序，在给定岛屿信息的情况下，计算对于每种参加人数，会议的最大期望得分。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$N$ $A_1$ $B_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$

输出格式

向标准输出写入 $N$ 行。在第 $j$ 行（$1 \le j \le N$）中，输出有 $j$ 只海狸参加的会议的最大期望得分。

数据范围

• $1 \le N \le 200\,000$
• $1 \le A_i \le N$ ($1 \le i \le N-1$)
• $1 \le B_i \le N$ ($1 \le i \le N-1$)
• $A_i \neq B_i$ ($1 \le i \le N-1$)
• 可以通过桥梁在任意两个岛屿之间往来。

子任务

1. (4 分) $N \le 16$
2. (16 分) $N \le 4\,000$
3. (80 分) 无附加限制。

样例

输入格式 1

5
1 2
2 3
4 2
3 5

输出格式 1

1
4
1
2
1

说明

例如，考虑居住在岛屿 $1$ 和岛屿 $3$ 的海狸参加的会议。 对于每个岛屿，它们需要经过的桥梁数量之和计算如下： 如果它们在岛屿 $1$ 集合，岛屿 $1$ 的海狸不需要经过桥梁，岛屿 $3$ 的海狸需要经过 $2$ 条桥梁。总和为 $2$。 如果它们在岛屿 $2$ 集合，总和为 $2$。 如果它们在岛屿 $3$ 集合，总和为 $2$。 如果它们在岛屿 $4$ 集合，总和为 $4$。 * 如果它们在岛屿 $5$ 集合，总和为 $4$。

会议地点的候选岛屿为 $1, 2, 3$。因此，该会议的期望得分为 $3$。

输入格式 2

7
1 2
2 3
3 4
4 5
2 6
3 7

输出格式 2

1
5
1
3
1
2
1