请升级 HydroOJ 到 4.19.0 以上版本以正常使用此插件功能。
从叶子走到根(hard)
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有一棵以节点1为根节点的树，树的每个叶子节点上都有一个虫子，每个虫子都会先后朝着根节点爬行，每当一个虫子到一个无所有者的节点，就会将这个节点收入麾下，并获得1块钱。
当一个虫子爬到了根节点，或者爬到有所有者的节点，就停止爬行。
前一个虫子爬完了，后一个虫子才能开始爬。
你可以决定虫子的爬行顺序，请尽可能让最穷的虫子拥有的钱最多。
格式
- 多组输入
输入格式
第一行输入一个正整数，表示一共有个测试样例
对于每个测试样例
-
第一行是一个整数，表示树一共有个节点
-
接下来行，每行有两个整数，代表节点u和节点v之间有一条边
输出格式
对于每个测试样例，输出一个正整数，表示最穷的虫子可能拥有的最多的钱是多少。
样例
3
5
1 2
1 3
3 4
3 5
3
1 2
2 3
1
1
3
1