题目描述

河狸们居住在 $N$ 个岛上，这些岛从 $1$ 到 $N$ 编号，并通过 $N-1$ 座双向连接的桥连通。桥的编号为 $1$ 到 $N-1$，桥 $i$ 连接岛 $A_i$ 和 $B_i$。任意两个岛之间都可以通过桥到达。

每个岛上有一只河狸。

有时，某些岛上的河狸要聚集到一个岛上开会。当一场会议的出席者确定后，满足以下条件的岛会被选为开会地址：

所有参会者为了到达这个岛所需要经过的桥的数量的总和最小。

这里，每位出席者都会走最短路径（经过最少桥的路径）前往开会岛。

会议出席者希望会议的候选岛很多。当出席者确定时，这场会议的期待值等于满足上述条件的岛的个数。

对于每个 $j = 1, 2, \dots, N$，你想知道当有 $j$ 位河狸参会时，最大的期待值是多少。

---

输入格式

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $A_i, B_i$，表示桥 $i$ 连接的两个岛。

---

输出格式

输出 $N$ 行，第 $j$ 行输出当参会者有 $j$ 位时，最大的期待值。

---

样例 1

输入

5
1 2
2 3
4 2
3 5

输出

1
4
1
2
1

解释

例如，考虑居住在岛 $1$ 和岛 $3$ 的河狸参加的会议。对于每个岛，他们经过桥的数量之和如下：

• 岛 $1$：$0 + 2 = 2$
• 岛 $2$：$1 + 1 = 2$
• 岛 $3$：$2 + 0 = 2$
• 岛 $4$：$2 + 2 = 4$
• 岛 $5$：$3 + 1 = 4$

总和最小的岛为 $1, 2, 3$，因此期待值为 $3$。

---

样例 2

输入

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

输出

1
5
1
3
1
2
1

---

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• 图是连通的

---

子任务

子任务编号	附加条件	分值
1	$N \le 16$	4
2	$N \le 4\,000$	16
3	无附加限制	80

---