Description

自从生化危机爆发后，这个世界上就充满了僵尸。
世界上共有\(n\)个城市和\(n-1\)条双向道路，任意两个城市都可以通过一条或多条道路相互到达。
如果保护伞公司在一个城市设立了\(D\)级基地，那么这个基地可以处理所有从这个城市出发经过不超过\(D\)条道路可以到达的城市的生化灾害。当然，同一个城市可以位于多个基地的影响范围内，这样更保险。
由于管理上的一些问题，保护伞公司只能设立\(k\)个基地，因此公司高层希望这些基地影响范围能够覆盖所有城市，并且其中最大的基地级别最小。
目前公司高层并不是很确定需要设立多少基地，因此对于\(1-n\)中的每个\(k\)你均需要输出对应的答案。

Format

Input

每个测试点包含多组输入数据。
第一行一个整数\(T\)，表示数据组数。
每组数据第一行一个整数\(n(1<=n<=100000)\)。
接下来\(n-1\)行，每行两个整数\(u,v\)，表示城市\(u\)和城市\(v\)之间有一条道路。
保证任意两个城市可以通过一条或多条道路相互到达。
所有数据中\(n\)的和不超过\(100000\)。

Output

按照输入顺序，对于每组数据输出一行用空格隔开的\(n\)个整数，表示\(k\)为\(1-n\)时对应的最大基地级别，行末请不要输出多余空格。

Sample 1

Input

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

Output

2 2 1 1 1 1 0
3 2 1 1 1 1 0

Limitation

5s, 1GB for each test case.

Hints

vijos上栈空间较小，请避免过多层数的递归调用。

Source

Vijos Original