Optimal Railroad Ticket Strategy

A railroad network in a nearby country consists of \( n \) cities numbered \( 1 \) through \( n \), and \( m \) two‐way railroad tracks connecting different pairs of cities. Each city has an automated ticket machine that works in a faulty way. When you insert a coin in the machine at city \( a \), it dispenses a one‐way ticket from \( a \) to one of its neighboring cities, chosen uniformly at random. Moreover, different tickets purchased at the same city are independent in their randomness.

A computer science student wants to travel from city \( 1 \) (her home) to city \( n \) (where a regional programming contest is taking place). At any city, when she purchases a ticket, she may either immediately use it to travel to the destination or discard it and try for another ticket. She can purchase tickets indefinitely. The journey ends as soon as she reaches city \( n \). The student has devised a strategy satisfying the following properties:

• The probability that the trip eventually finishes is \( 1 \).
• The expected number of coins spent is minimized.

Your task is to compute the minimum expected number of coins the student will spend to travel from city \( 1 \) to city \( n \).

Hint: Let \( dp[i] \) denote the minimum expected cost starting from city \( i \). Note that for \( i\neq n \), if city \( i \) has \( deg(i) \) neighbors and you already know the answers (i.e. \( dp \) values) for some neighbors, then an optimal strategy yields the recurrence

[ dp[i] = 1 + \frac{1}{deg(i)}\Big(\sum_{\substack{j\text{ neighbor of } i\ dp[j] < dp[i]}} dp[j] + \big(deg(i)-k\big),dp[i]\Big), ]

where \( k \) is the number of neighbors \( j \) with \( dp[j] < dp[i] \). Rearranging gives

[ dp[i] = \frac{deg(i) + \sum dp[j]}{k}, ]

for an appropriate choice of neighbors. An efficient method is to reverse the process starting from city \( n \) (with \( dp[n] = 0 \)) and update the expected values for other cities using a Dijkstra‐like algorithm.

inputFormat

The first line contains two integers \( n \) and \( m \) \( (2 \leq n \leq 10^5,\ 1 \leq m \leq 3\cdot10^5) \) --- the number of cities and railroad tracks respectively.

Each of the next \( m \) lines contains two integers \( a \) and \( b \) \( (1 \leq a, b \leq n,\ a \neq b) \) indicating there is a two-way railroad track between cities \( a \) and \( b \). It is guaranteed that it is possible to travel from city \( 1 \) to city \( n \) by some sequence of tracks.

outputFormat

Output a single number: the minimum expected number of coins required to travel from city \( 1 \) to city \( n \). Your answer will be considered correct if its absolute or relative error does not exceed \( 10^{-6} \).

sample

3 3
1 2
2 3
1 3

2.0000000000