Lester 和 Delbert 已经知道如何通过炸毁最少数量的铁路来切断铁路网。这被证明相当容易，于是他们继续研究另一个有趣的问题：如何抢劫联邦银行。现在他们需要你的帮助来制定逃跑计划。

银行位于一个城市中，该城市有 $N$ 个交叉路口和 $N-1$ 条连接它们的双向道路。所有道路的长度相同。通过道路网络，可以从任意一个交叉路口到达其他任何交叉路口。

为了确保安全逃脱，Lester 和 Delbert 计划雇佣 $K$ 个警戒小组，并将它们放置在不同的交叉路口，以收集有关警察动向的信息。一旦确定了放置位置，对于每一个交叉路口，他们会计算到达最近的警戒小组所需经过的最少道路数量。在所有交叉路口中，该值的最大值被称为当前放置方案的“威胁等级”。

Lester 想只雇佣一个警戒小组，而 Delbert 则倾向于使用 $N$ 个。由于最终的方案很可能介于两者之间，他们请求你计算对于每一个可能的 $K$ 值，所能达到的最小威胁等级。

输入格式

输入的第一行包含一个整数 $N$，表示城市中交叉路口的数量 ($1 \le N \le 150\,000$)。接下来的 $N-1$ 行包含道路的描述。每行描述包含两个整数 $u$ 和 $v$，表示这两个交叉路口之间有一条道路 ($1 \le u, v \le N, u \neq v$)。保证可以通过道路网络从任意一个交叉路口到达其他任何交叉路口。

输出格式

输出必须包含 $N$ 个整数。其中第 $i$ 个整数必须等于使用恰好 $i$ 个警戒小组时所能达到的最小威胁等级。

样例

输入格式 1

10
7 3
6 9
9 7
1 7
10 7
8 5
4 1
5 9
2 5

输出格式 1

3 2 2 1 1 1 1 1 1 0

说明

下表描述了上述样例：

• 警戒小组数量 1：最优放置方案 {7}，最优距离 3
• 警戒小组数量 2：最优放置方案 {7, 9}，最优距离 2
• 警戒小组数量 3：最优放置方案 {1, 5, 6}，最优距离 2
• 警戒小组数量 4：最优放置方案 {1, 5, 7, 9}，最优距离 1
• 警戒小组数量 5：最优放置方案 {1, 5, 7, 9, 10}，最优距离 1
• 警戒小组数量 6：最优放置方案 {1, 5, 7, 8, 9, 10}，最优距离 1
• 警戒小组数量 7：最优放置方案 {1, 5, 6, 7, 8, 9, 10}，最优距离 1
• 警戒小组数量 8：最优放置方案 {1, 4, 5, 6, 7, 8, 9, 10}，最优距离 1
• 警戒小组数量 9：最优放置方案 {1, 3, 4, 5, 6, 7, 8, 9, 10}，最优距离 1
• 警戒小组数量 10：最优放置方案 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}，最优距离 0