Description

在一个神秘的花园中，有 $n$ 朵神奇的花朵，这些花朵通过 $n-1$ 根魔法树枝相连。第 $1$ 朵花是花园中最高的花朵，所有其他的花都能通过树枝与这朵最高的花直接或间接地连接。

每朵花都有一个盛开度和美丽值。你可以为每朵花分配一个盛开度，使得所有花的盛开度构成一个 $1$ 到 $n$ 的排列。一朵花的美丽值定义为从该花到最高花的简单路径上所有花朵盛开度的中位数，其中中位数定义为将一个包含 $m$ 个数的序列从大到小排序后的第 $\left\lfloor\dfrac{m}{2}\right\rfloor$ 个数。

花园的主人想要采摘 $k$ 朵花作为礼物，他希望被采摘的 $k$ 朵花中美丽值最小的那朵花的美丽值尽可能大。你需要对于 $k=1,2,3,\ldots,n$ 分别求出这个最大值是多少。注意，对于不同的 $k$ 值，可以为花朵重新分配盛开度。

Format

Input

第一行包含一个整数 $T$，表示测试数据的组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

• 第一行包含一个正整数 $n$，表示花朵的数量。
• 接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示第 $u$ 朵花和第 $v$ 朵花之间有一根树枝连接。

Output

对于每组测试数据输出一行，包含 $n$ 个整数，其中第 $i$ 个整数表示 $k=i$ 时的答案。

Samples

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

8 8 8 7 7 7 7 6
12 12 12 12 11 11 11 10 10 9 9 9

Limitation

$1\mathrm{s},512\mathrm{MB}$

Subtasks

特殊性质：令 $\mathrm{deg}_i$ 表示与第i朵花直接相连的花朵数量，对于所有 $i\in \left[2,n\right]$，满足 $\mathrm{deg}_i\leqslant 2$。

对于所有测试数据，保证 $1\leqslant T\leqslant 100$，$1\leqslant n,\sum n\leqslant 10000$，$1\leqslant u,v\leqslant n$。