Description

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

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

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

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

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

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

输出这个期望值。

Input Format

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

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

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

Output Format

输出一个数，为期望值。此输出只要与正解的相对差或绝对差小于 $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