题目背景

$$第26次新生$$

昏黄的灯光在地下室里摇曳，巴尔克用扳手撬开 $25$ 号的胸腔，金属撕裂的声响，宣告这成为第 $25$ 个失败品。

一个阴雨绵绵的四月天，他将亡女的蝴蝶结缝在 $26$ 号的胸前，企鹅状的铁皮躯体突然发出齿轮咬合的嗡鸣。

$$初见$$

地下室通风管道的锈味混进一丝草莓香，透过缝隙，我看到一双缀着蝴蝶结的小皮鞋。一个穿着白色连衣裙的小女孩走向我，我从未见过她。

“你比爸爸的怀表有趣多了！”小女孩趴在操作台上，将一颗糖果塞进我手中。

“叫你邦邦好不好？”她将手放在我胸前的蝴蝶结上，似乎在感受机械心脏的跳动。

巴尔克警告过我不能与“实验无关人员”互动，但当她第 $7$ 次溜进地下室时，我擅自生成了一个协议——在检测到穿着白色连衣裙的女孩时，启动微笑程序。

$$未送出的花$$

我又闻到了那股她身上独有的草莓香，但这一次，我没有见到她。树上的花开得正好，我折下一朵，期待与她相遇之时送出。

那晚的警报响了整夜，巴尔克决不允许我浪费 $1\%$ 的能源在无意义的事上。巴尔克更换了我的中央枢纽，修改了规则，我失去了记忆。

$$很高兴认识你，邦邦！$$

每次重启后，我都会无意识地播放同一句话：“很高兴认识你，邦邦！”巴尔克为此十分苦恼。

看见地上散落一地的花瓣，我的心里空落落的。我甚至忘却了自己名字的由来！为了寻求答案，我来到了庄园……

$$庄园游戏$$

我参与了第十场游戏，游戏中有一位穿着白色连衣裙的女孩，她身上的草莓香令我倍感熟悉。不知为何，每次看见她，我都会启动微笑程序。

一场大火烧毁了一切，不归林被夷为平地，那是我最后见到她的地方。

$$尾声$$

未送出的花成为了邦邦破灭的梦想。

他从来没真正删除那段记录。

影像记录 $0$：穿着白色连衣裙的女孩笑着说：“很高兴认识你，邦邦！”

题目描述

树上开了 $n$ 朵花，花之间由 $n-1$ 根树枝连接。第 $1$ 朵花是树上最高的花，每朵花都可以通过树枝与最高的花直接或间接地连接。

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

邦邦想折下 $k$ 朵花送出，使送出的 $k$ 朵花中美丽值最小的花美丽值尽可能大。你需要对于 $k=1,2,3,\dots,n$ 分别求出这朵花的美丽度是多少，$k$ 不同时花朵的盛开度可以不同。

输入格式

本题有多组测试数据。

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

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

• 第一行包含一个正整数 $n$，表示花朵的数量。

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

输出格式

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

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

提示

【样例解释】

对于第一组测试数据，每朵花的盛开度为 $8,7,6,5,4,3,2,1$ 时，每朵花的美丽值分别为 $8,8,8,7,7,6,7,7$，此时对于所有 $k$ 均满足题目的要求。

【数据范围】

本题采用捆绑测试。

记 $\sum n$ 表示单个测试点中 $n$ 的和。

$\text{Subtask}$	$\sum n\le$	特殊性质	分值
$1$	$10$	无	$10$
$2$	$20$		$20$
$3$	$400$		$30$
$4$	$10^4$	有	$10$
$5$		无	$30$

• 特殊性质：令 $deg_i$ 表示与第 $i$ 朵花直接相连的花的数量，$\forall i\in[2,n]$，$deg_i\le 2$。

对于所有的测试数据，保证：$1\le T\le 100$，$1\le n,\sum n\le 10^4$，$1\le u,v\le n$。