Hypno

You have just heard that a new PokéStop has opened somewhere in your city. You want to go there and collect the items it offers. The city has $n$ intersections connected by $m$ bidirectional roads, numbered from 1 to $n$. You are at intersection 1, and the PokéStop is at intersection $n$. Crossing any road takes one minute.

Each road has a single Hypno. When you reach the midpoint of a road, the Hypno uses its psychic power on you, and you fall into a very short sleep. The Hypno then makes you sleepwalk to a random endpoint of that road. After one minute, you are at the opposite end with probability $\frac{1}{2}$, or back at the same intersection otherwise.

You are immune to each individual Hypno with probability $\frac{1}{2}$. If the road you are on has a Hypno you are immune to, you always cross the road safely in one minute. If it has a Hypno you are susceptible to, you fall asleep on every crossing of that road. You do not know initially which roads have which Hypno, but after you attempt to cross a road, you know which endpoint you are currently at. What is the minimum expected time to reach the PokéStop at intersection $n$?

The first line contains two integers $n$ and $m$ ($2 \le n \le 200000$, $1 \le m \le 200000$), the number of intersections and the number of roads. Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), the intersections connected by a road. No two intersections are connected by more than one road. The city is connected, so you can reach every intersection from every other intersection.

Print a single real number, the minimum expected time to reach intersection $n$. Your answer is correct if its absolute or relative error does not exceed $10^{-9}$.

In the first sample, the optimal strategy is to repeatedly try to go directly to the destination using the second road. With probability $\frac{1}{2}$, you are immune to the Hypno on that road and reach the destination in 1 minute. Otherwise, you are susceptible, and the expected time in that case is $\frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \frac{1}{16} \cdot 4 + \cdots = 2$. The overall expected time is $\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 = \frac{3}{2}$.

In the second sample, repeatedly trying the second intersection takes 3 minutes in expectation. Trying only the third intersection also takes 3 minutes. A better strategy exists.