Gambling Guide

A railroad network in a nearby country has $n$ cities numbered 1 to $n$ and $m$ two-way tracks, each of which joins two different cities. Tickets are sold only by the automated machines installed in every city. Hackers tampered with those machines, so every one of them now works like this: when a single coin is inserted into the machine in city $a$, the machine prints one one-way ticket from $a$ to a neighbouring city, chosen uniformly at random among all cities joined to $a$ by a track. Destinations of different tickets bought in the same city are independent.

A computer science student has to travel from city 1, where she lives, to city $n$, where a regional programming contest has already started. She knows how the machines work, though she cannot predict the random choices, and she has a map of the railroad network. After buying a ticket she reads the destination printed on it, and she can either use the ticket at once and travel to that city, or throw the ticket away and buy a new one in the city she is standing in. She can keep buying tickets forever. The trip ends the moment she reaches city $n$.

After some calculation she found a travel strategy with these two properties:

• The probability that the trip eventually ends is $1$.
• The expected number of coins spent on the trip is as small as possible.

Find the expected number of coins she will spend.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 300000$), the number of cities and the number of railroad tracks.

Each of the next $m$ lines contains two different integers $a$ and $b$ ($1 \le a, b \le n$), describing a track that joins city $a$ and city $b$. Each pair of cities is joined by at most one track. City $n$ is reachable from city 1.

Print the expected number of coins, rounded to exactly $10$ digits after the decimal point, on one line.

The figure shows the railroad network of the second example.