There are N number,they are respectively from 1 to N.
for a set of numbers, we set a problem as flow:
we assume that the initial position of each number is the corresponding positon on number axis.
Then what we have to do is to make the minimum and maximum number of meet in minimum time.
We can operate these numbers as flow:
Each operation, we can select two adjacent numbers on the number axis and exchange them.multiple operations can be performed at the same time.
the time it spend is the distance between two position.
When the minimum and maximum number went to the adjacent positions,the time of they meet is distance/2.
Here is an example:
1..4......11....16..19
We want 1 and 19 meet.
Let 1,4 and 16,19 exchange, they can be performed at the same time and end at the same time.It spend 3 units time,and becomes the following:
4..1......11....19..16
Then there are two Plan:
A Plan:
let 1 and 11 exchange with 7 units time first.And it becomes the following:
4..11......1....19..16
Then exchange 1 and 19 with 2.5 units time.
the total times is:3+7+2.5=12.5
Plan B:
Let 11 and 19 exchange with 5 units time first.it becomes the following:
4..1......19....11..16
let 1 and 19 exchanged with a time of 3.5 units.
total:3+5+3.5=11.5
Clearly, B Plan work better.
Now everyone seems to understand the meaning of the problem.
So the question now is like the following
at the beginning, there are N sets, the i-th set contains and contains only i.
Then N-1 operations flow:
Merge two set.
And you should calculate the minimum time of making the biggest and smallest number meet after merging in this set.
Input
The first line contains a number T(T<=5), indicating T cases of data.
for each case of data:
The first line contains a number N.
Then N-1 lines flow,
each line contains two different integers u, v.
they Represents we merge two set where u and v are.
we promise that u and v are not at the same set.
* $1 \leq N \leq 300000$
Output
for each case of data:
for each line, output the minimum time after merging, accurated to 0.01.
