抵抗组织正试图控制特定太阳系中尽可能多的行星。海蒂公主负责掌管舰队,她必须派遣船只前往一些星球,以便最大限度地控制星球数量。
银河系包含 N 个行星,通过双向超空间隧道连接,每对行星之间都有一条独特的路径。
如果一颗行星的轨道上有抵抗军飞船,或者该行星位于轨道上有抵抗军飞船的两颗行星之间的最短路径上,则该行星将受到抵抗军的控制。
海蒂还没有决定使用多少艘船。因此,她要求你计算,对于每个 K = 1, 2, 3, ..., N,由 K 艘船组成的舰队可以控制的最大行星数量。
输入
输入的第一行包含一个整数 N (1 ≤ N ≤ 105) – 星系中行星的数量。
接下来的 N - 1 行描述了行星之间的超空间隧道。 N - 1 行中的每一行包含两个空间分隔的整数 u 和 v (1 ≤ u, v ≤ N),表示行星 u 和 v 之间存在双向超空间隧道。保证每两个行星都由一条隧道路径连接,并且每条隧道连接不同的一对行星。
输出
在一行上打印 N 个空格分隔的整数。第 K 个数字应该对应于抵抗组织使用 K 艘船队可以控制的最大行星数量。
示例
输入 #1
3 1 2 2 3
输出 #1
1 3 3
输入 #2
4 1 2 3 2 4 2
输出 #2
1 3 4 4
注意
考虑第一个例子。如果K=1,那么海蒂只能派遣一艘船到某个星球并控制它。然而,当 K ≥ 2 时,向 1 号和 3 号行星派遣船只将允许抵抗军控制所有行星。