Problem Description
Finally Biaoge reached the amusement park. But soon he got lost…
The amusement park has N sites and N bidirectional roads connecting these sites. You can start from every site to get to any other site through the roads. Every time Biaoge got to a site, he marked it as visited and then chose a new site which was connected directly to it and not visited yet. If there were more than one site meet the conditions, Biaoge would choose randomly with equal possibility.
Biaoge also chose the first site among N sites randomly with equal possibility and then repeated this process until there was no site to go.
Calculate the possibility for each site of being the last site which Biaoge would visit. And output the sum of five largest possibilities.
Input
There are multiple test case.
For each test case the first line contains an Integer N(5≤N≤100000) indicating the number of sites(All sites are labeled from 1 to N) . And then N lines follow. Each line contains two Integer x,y(1≤x,y≤N)indicating two sites connected by the road.
The input end with N=0.
Obviously there is exactly one loop in the abstracted graph. It is guaranteed that the length of loop is between 3 and 30.
Output
For each case, output the sum of five largest possibilities in a single line. The answer should be rounded to 5 digits after decimal points.
Sample Input
5
5 2
2 4
4 5
3 4
1 2
10
5 8
8 3
3 1
1 5
2 1
10 8
7 8
6 7
4 10
9 10
0
Sample Output
1.00000
0.91250
