给你一棵树(没有循环的连通图),其顶点为 $$$n$$$。
考虑一个固定整数$$$k$$$。那么,图 $$$G_k$$$ 是一个具有 $$$n$$$ 个顶点的无向图,其中当且仅当给定树中顶点 $$$u$$$ 和 $$$v$$$ 之间的距离至少为 $$$k$$$ 时,顶点 $$$u$$$ 和 $$$v$$$ 之间存在边。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,打印图中 $$$G_k$$$ 中连通分量的数量。
输入
第一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 图中的顶点数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),表示树中顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成一棵有效的树。
输出
输出 $$$n$$$ 整数:$$$G_k$$$ 图中每个 $$$k$$$ 从 $$$1$$$ 到 $$$n$$$ 的连通分量数。
示例
输入 #1
6 1 2 1 3 2 4 2 5 3 6
输出 #1
1 1 2 4 6 6
输入 #2
5 1 2 2 3 3 4 3 5
输出 #2
1 1 3 5 5
注意
在第一个示例中:如果 $$$k=1$$$,则该图在每对顶点之间都有一条边,因此它有一个分量。如果 $$$k=4$$$,则该图仅具有边 $$$4 \leftrightarrow 6$$$ 和 $$$5 \leftrightarrow 6$$$,因此该图具有 $$$4$$$ 个分量。
在第二个示例中:当 $$$k=1$$$ 或 $$$k=2$$$ 时,该图只有一个分量。当 $$$k=3$$$ 时,图 $$$G_k$$$ 分为 $$$3$$$ 组件:一个组件具有顶点 $$$1$$$、$$$4$$$ 和 $$$5$$$,另外两个组件各包含一个顶点。当 $$$k=4$$$ 或 $$$k=5$$$ 时,每个顶点都是一个单独的组件。