Bonus 奖励计划

时间限制:3s      空间限制:64MB

题目描述


输入格式

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


输出格式

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


样例输入

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

样例输出

1.000000
0.888889
0.750000
0.840000

提示

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


题目来源

北京2010