merge

有N个数，分别为1~N，对于一个数集，我们定义一下问题：
假设一开始每一个数都在数轴对应位置上，然后我们要做的是要让最小的数和最大的数相遇，并求相遇最小时间。
我们这样操作这些数：
每次操作可以选择两个数轴上相邻数交换，多个操作可以同时进行，但不能对一个数同时进行两个交换操作。
交换时间就是两个数在数轴上的距离，因为每个数一个单位时间移动一个单位距离，一个交换操作中途两个数不能停下来，不能改变交换对象，直到两个数交换了位置。
当最小的数和最大的数走到了相邻位置时，他们相遇的时间就是距离/2，因为交换中途就会相遇。
相遇完后，数的位置恢复原状。
下面举一个例子：
1..4......11....16..19
我们要让1和19相遇
首先让1、4和16、19交换，他们可以同时进行，而且恰好同时结束了。用时3个单位，然后变成下面这样：
4..1......11....19..16
接下来有两种情况：
A方案：
先让1和11先交换，19不动，那么用时7个单位，然后变成下面这样：
4..11......1....19..16
再交换1和19，用时2.5个单位。
加起来是这样的：3+7+2.5=12.5
B方案：
先让11和19交换，1不动，那么用时五个单位，且变成下面这样：
4..1......19....11..16
再用1和19交换，所用的时间是3.5个单位。
加起来是这样的：3+5+3.5=11.5
很明显B方案更优。
所以最少用时是11.5。
看样子大家都读懂题意了。
那么现在问题是这样的：一开始有N个数集，第i个数集就有且仅有i这个元素。
那么N-1个操作：每次合并两个数集，并且要你求出这个数集里面最小最大数相遇最小时间。
怎么样，很有挑战性吧？快点来挑战吧~。

第一行一个数T（T<=5）。表示数据组数。
第一行一个数N，含义上面有说。
接下来N-1行，每行两个不同的整数u,v
表示将u所在点集和v所在点集合并，这里保证u和v在两个不同的集合里头。
$1 \leq N \leq 300000$

对于每组数据：
N-1行，输出每次合并，输出要求的答案，保留一位小数。

1
3
1 2
1 3

0.5
1.5