题目描述

A railroad network in a nearby country consists of $n$ cities numbered $1$ through $n$, and $m$ two-way railroad tracks each connecting two different cities. Tickets can only be purchased at automated machines installed at every city. Unfortunately, hackers have tampered with the ticket machines and now they all work as follows: when a single coin is inserted in the machine installed at city $a$, the machine dispenses a single one-way ticket from $a$ to a random neighboring city. More precisely, the destination city is chosen uniformly at random among all cities directly connected to a with a railroad track. Destinations on different tickets originating in the same city are independent.

A computer science student needs 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 (but of course cannot predict the random choices) and has a map of the railway network. In each city, when she purchases a ticket, she can either immediately use it and travel to the destination city on the ticket, or discard the ticket and purchase a new one. She can keep purchasing tickets indefinitely. The trip is finished as soon as she reaches city $n$.

After doing some calculations, she has devised a traveling strategy with the following properties:

• The probability that the trip will eventually finish is $1$.
• The expected number of coins spent on the trip is the smallest possible.

Find the expected number of coins she will spend on the trip.

输入格式

The first line contains two integers $n$ and $m(1 \le n,m \le 300 000)$ — the number of cities and the number of railroad tracks. Each of the following $m$ lines contains two different integers $a$ and $b(1 \le a, b \le n)$ which describe a railroad track connecting cities $a$ and $b$.

There will be at most one railroad track between each pair of cities. It will be possible to reach city $n$ starting from city $1$.

输出格式

Output a single number — the expected number of coins spent. The solution will be accepted if the absolute or the relative difference from the judges solution is less than $10^{-6}$.

题目大意

一个铁路系统由 $n$ 个城市和 $m$ 条双向铁路组成。铁路票只能在安装在每个城市的自动售票机购买。不幸的是，黑客们已经篡改了这些售票机，现在它们有下面的规则：

当 $a$ 市的售票机有一个硬币投入时，机器会发一张从 $a$ 市到随机一个邻市的单程票。

你需要从城市 $1$ 到城市 $n$。你知道机器是怎么工作的并且有一份铁路系统的地图。在每一个城市，当你买了一张票时，你可以选择立即使用它后到达目的地，或者是丢掉它并买一张新票。你可以无限制的购买的票。当你到达城市 $n$，旅行就会结束。

你需要确定一个满足以下条件的策略：

• 旅行最终到达终点的概率为 $1$。

• 花在旅行上的硬币的期望值越少越好。

输出这个期望值。

【输入格式】

第一行包含两个整数 $n$ 和 $m(1 \le n,m \le 300000)$。

接下来 $m$ 行每行包含了两个不同的整数 $a$ 和 $b(1 \le a,b \le n)$，描述了一条连接 $a$ 市和 $b$ 市的双向铁路。

两个城市之间最多只会有一条铁路，输入保证有一条从城市 $1$ 到 $n$ 的路径。

【输出格式】

输出一个数，为期望值。此输出只要与正解的相对差或绝对差小于 $10^{−6}$ 就可以通过。

4 4
1 2
1 3
2 4
3 4

3.0000000000

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

4.1111111111