Andrey 非常关心俄罗斯偏远地区的孩子们，他们因为附近没有数学学校而无法接受良好的教育。他梦想着开办一所带有宿舍的特殊学校，让天才儿童们可以在那里共同生活和学习，并由莫斯科国立大学的教授担任教师和导师。他决定在全国各地旅行，与不同的人交谈，看看他们是否喜欢这个想法。
他刚刚抵达新西伯利亚（Nsk），他应该去参观该镇唯一的学校，并发表一场鼓舞人心的演讲。他时间紧迫，所以他想尽快从当前位置到达学校。
新西伯利亚有 $N$ 个交叉路口，由 $M$ 条双向道路连接。在任何直接相连的交叉路口之间行走需要正好一分钟。每条道路连接两个不同的交叉路口，没有一对交叉路口由多于一条道路直接连接，且每对交叉路口之间都是直接或间接连通的。
Andrey 从交叉路口 1 开始他的旅程，前往学校所在的交叉路口 $N$。你能帮他计算他走到目的地所需的最少分钟数吗？当然你可以，但这并不是问题的全部。
学校校长对这次访问并不高兴，并计划让 Andrey 的演讲尽可能短。他知道这位著名的数学家非常怕黑，所以为了达到他残酷的目的，校长关掉了几乎所有的路灯。现在，每一时刻只有一条道路是亮着的。此外，哪条道路是亮着的可能会每分钟改变一次。更具体地说，会发生以下情况：
- 在每一分钟开始时，从所有 $M$ 条可能的道路中随机且均匀地选择一条道路。
- 这条道路将在当前这一分钟内被照亮。
- 如果 Andrey 站在与亮着的道路相连的交叉路口，他可以选择使用这条道路到达另一端。他也可以选择在这一分钟内原地不动。Andrey 不能使用除亮着的道路以外的其他道路。
假设 Andrey 对图的情况了如指掌并采取最优策略，计算他到达目的地所需的期望分钟数。
输入格式
输入的第一行包含交叉路口的数量 $N$ 和双向道路的数量 $M$ ($1 \le N, M \le 100\,000$)。
接下来的 $M$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示由该道路连接的一对交叉路口 ($1 \le a_i, b_i \le N, a_i \neq b_i$)。保证从任何交叉路口都可以到达其他任何交叉路口，且图中没有自环或重边。
输出格式
输出一个实数，表示如果 Andrey 采取最优策略，他从交叉路口 1 到达交叉路口 $N$ 所需的期望分钟数。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则被认为是正确的。
形式上，如果你的答案是 $A$，裁判的答案是 $B$，如果满足 $\frac{|A-B|}{\max(1, B)} \le 10^{-6}$，则检查器将接受你的答案。
样例
样例输入 1
3 2 1 2 2 3
样例输出 1
4.0000000000
样例输入 2
4 4 1 2 2 4 1 3 3 4
样例输出 2
6.0000000000
说明
在第一个样例中，Andrey 可以采取以下策略：
- 起初他停留在交叉路口 1。
- 他等待直到道路 (1, 2) 被照亮，并利用它到达交叉路口 2。平均等待时间为 2.0 分钟。
- 站在交叉路口 2，他等待直到道路 (2, 3) 被照亮，并利用它到达交叉路口 3。这也需要平均 2.0 分钟的等待时间，因此到达目的地的期望时间为 4.0 分钟。
在第二个样例中，Andrey 可以采取以下方式：
- 起初他停留在交叉路口 1。
- 他等待直到道路 (1, 2) 或 (1, 3) 中的一条被照亮，并分别利用它到达交叉路口 2 或 3。这需要平均 2.0 分钟的等待时间。
- 现在他停留在交叉路口 2 或 3，在这两种情况下，他都只需要等待直到通往交叉路口 4 的道路被照亮。这需要平均 4.0 分钟的等待时间，因此到达学校的期望时间为 6.0 分钟。