树是一种无向图,每对顶点之间只有一条简单路径。如果树的每个顶点属于这些路径(包括端点)中的一个以上,并且每个路径恰好由 $$$k$$$ 个顶点组成,则我们称一组简单路径 $$$k$$$ 有效。
给你一棵有 $$$n$$$ 个顶点的树。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,找出 $$$k$$$ 有效简单路径集的最大可能大小。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100\,000$$$) — 树中的顶点数。
接下来的 $$$n - 1$$$ 行描述了树,每行包含两个整数 $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$) — 相应边的端点。
保证给定的图是一棵树。
输出
输出 $$$n$$$ 数字,其中第 $$$i$$$ 是 $$$i$$$ 有效路径集中的最大可能路径数。
示例
输入 #1
7 1 2 2 3 3 4 4 5 5 6 6 7
输出 #1
7 3 2 1 1 1 1
输入 #2
6 1 2 2 3 2 4 1 5 5 6
输出 #2
6 2 2 1 1 0
注意
下图说明了实现第二个样本的最佳路径数的一种方法: