1989 - Bonus 奖励计划

Input

请做到文件底结束,对于每一组：第一行包含一个正整数N，表示城市的数目。接下来的N-1行，每行包含2个整数，Ai、Bi，表示Ai和Bi间有一条双向的旅行通道。

Output

对于每一组测试数据，输出一行：为一个实数，表示平均的支付费用，保留（四舍五入）至小数点后6位。

Examples

Input

2
1 2
3
1 2
2 3
4
1 2
1 3
1 4
5
1 2
5 2
2 3
4 3

Output

1.000000
0.888889
0.750000
0.840000

Hint

10%的数据中N ≤ 10； 30%的数据中N ≤ 100； 50%的数据中N ≤ 1000。 100%的数据中2 ≤ N ≤ 10000，T ≤ 10，1 ≤ Ai，Bi ≤ N，Ai≠Bi。 数据保证任意两个城市之间有且只有一条路径（Path）。

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题