Description

The Flea Kingdom is developing its tourism industry vigorously, and every city has been built into a tourist attraction.

Many fleas want to travel to other cities, but because they jump rather slowly, their wishes are hard to achieve. At this time, Little C heard of a means of transport called a train, which runs very fast on railways. He seized the business opportunity, founded a railway company, and asked the Flea King for permission to build railways between every pair of cities.

However, since Little C does not know how to switch tracks, after a train arrives at a city, it can only guarantee that it will not return along the same route. Instead, it will randomly and uniformly go to another city that is connected to the current city by a railway.

The Flea King asked the public for opinions. As a result, the fleas were not very satisfied, because after building railways in this way, it is possible that they return after visiting only $3$ cities (including the starting city). They hope to visit more cities. Therefore, the Flea King required Little C to provide a plan so that each flea, after getting on a train, can visit more cities before returning.

Little C provided a plan to the Flea King. The Flea King wants to know, in this plan, the expected travel time for residents of each city (assume the time for the train to pass each railway segment is $1$). Please help the Flea King.

Input Format

The first line contains two positive integers $n$ and $m$, where $n$ is the number of cities and $m$ is the number of railway segments in the plan.

The next $m$ lines each contain two positive integers $u$ and $v$, indicating that there is a railway segment between city $u$ and city $v$ in the plan.

It is guaranteed that there are no multiple edges and no self-loops in the plan, every pair of cities is reachable directly or indirectly via railways, and after the train reaches any city through any railway segment, there is always at least one route to take.

Output Format

Output $n$ lines. The $i$-th line contains a real number $t_i$, representing the expected travel time for residents of city $i$ in the plan. You should output enough digits after the decimal point to ensure that the absolute or relative error between your output and the true value does not exceed $10^{-9}$.

Thanks to

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

3.333333333333
5.000000000000
3.333333333333
5.000000000000

10 15
1 2
1 9
1 5
2 3
2 7
3 4
3 10
4 5
4 8
5 6
6 7
6 10
7 8
8 9
9 10

10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000
10.000000000000

Hint

For $10\%$ of the test points, $n \le 10$.

For $20\%$ of the test points, $n \le 12$.

For $50\%$ of the test points, $n \le 16$.

For $70\%$ of the test points, $n \le 19$.

For $100\%$ of the test points, $4 \le n \le 21$, $1 \le u,v \le n$. The testdata has graded difficulty.

Time limit: 1 second, 256 MB. Lanqiao Cup 2017, the 8th National Contest.

Translated by ChatGPT 5