UOJ Logo Universal Online Judge

UOJ

附件下载 统计

Knight of Diamonds, wielding contractions to forge a tree of perfect face.

对于一棵有标号无根树,定义一次 收缩 操作 uv 为:

  • 如果 u,v 在当前树上不相邻则无事发生。
  • 否则如果 u,v 相邻,对于 v 的所有非 u 的邻居,将其和 u 之间连一条无向边,然后删除 v 和所有与其相连的边。

定义一棵有标号无根树为 无根满二叉树,当且仅当其可以通过选择一个结点作为根成为 满二叉树

现在给定一棵大小为 n 的有标号无根树 G,你想知道:可以通过若干次 收缩 操作变为树 G无根满二叉树,无根满二叉树原本的结点个数至少为多少。

可以证明始终存在一棵大小有限的无根满二叉树满足题目限制。

由于答案可能很大,假设答案为 s,你只需要输出 log2(s+1) 即可。可以证明 log2(s+1) 在题目的限制下始终为正整数。

(一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的高度为 k,且结点总数是 2k1,则它就是满二叉树。)

输入格式

第一行一个正整数 T,表示这个测试点内测试数据的组数。对于每组测试数据:

  • 第一行输入一个正整数 n

  • 接下来 n1 行,每行两个正整数 u,v 表示 G 上的一条边 (u,v)

输出格式

对于每组测试数据,输出一行一个正整数表示答案。

样例一

input

1
5
1 5
2 5
3 5
4 5

output

3

explanation

可以通过大小为 7 的无根满二叉树通过两次收缩得到。

样例二

input

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

output

2
4

样例三~七

见附件下载。

限制与约定

对于所有数据,保证 1n106

子任务编号 T n 树形态 分值
1 1 50 无特殊形态 15
2 1 5000 无特殊形态 15
3 1000 2×105 10
4 1000 2×105 菊花 10
5 5×105 5×105 无特殊形态 25
6 106 106 无特殊形态 25

“树形态”中,“菊花”指存在一个向所有点有直接连边的点,“链”指所有点度数不超过 2

时间限制:2s

空间限制:512MB