某国的铁路网包含 $n$ 个城市（编号为 $1$ 到 $n$）以及 $m$ 条连接两个不同城市的双向铁路。每个城市都安装了自动售票机，但由于黑客的破坏，售票机的工作方式如下：在城市 $a$ 投入一枚硬币，机器会随机发放一张从 $a$ 到某个相邻城市的单程票。具体来说，目的地城市是从所有与 $a$ 直接相连的城市中等概率随机选择的。从同一城市发出的不同票据，其目的地选择是相互独立的。

一名计算机专业的学生需要从她居住的城市 $1$ 前往城市 $n$（区域程序设计竞赛的举办地）。她了解机器的工作原理（当然无法预测随机选择的结果），并且拥有铁路网的地图。在每个城市，当她购买一张票时，她可以选择立即使用它前往票上的目的地城市，或者丢弃这张票并重新购买一张。她可以无限次购买票据。一旦到达城市 $n$，旅程即告结束。

经过计算，她制定了一种旅行策略，该策略具有以下特性： 旅程最终结束的概率为 $1$。 旅程中花费的硬币总数期望值最小。

求她完成旅程所需花费的硬币总数期望值。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 300\,000$)，分别表示城市数量和铁路条数。接下来的 $m$ 行，每行包含两个不同的整数 $a$ 和 $b$ ($1 \le a, b \le n$)，描述了一条连接城市 $a$ 和 $b$ 的铁路。每对城市之间最多只有一条铁路。保证从城市 $1$ 出发可以到达城市 $n$。

输出格式

输出一个数字，表示花费的硬币总数期望值。如果输出结果与标准答案的绝对误差或相对误差小于 $10^{-6}$，则该解将被接受。

样例

输入 1

4 4
1 2
1 3
2 4
3 4

输出 1

3.0000000000

输入 2

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

输出 2

4.1111111111

说明

样例 2 的示意图：