你刚刚听说城市里新开了一个 PokStop。你显然想去那里并获得可用的物品。这座城市由 $n$ 个交叉路口和 $m$ 条双向道路组成。交叉路口编号为 $1$ 到 $n$。你目前位于第一个交叉路口，而 PokStop 位于第 $n$ 个交叉路口。穿过每条道路需要一分钟。你以多快的速度能到达 PokStop？！

别急，没那么快。每条道路上都有一个催眠兽（Hypno），当你到达道路中点时，它就会准备对你使用超能力。一旦发生这种情况，你就会陷入短暂的睡眠。然后催眠兽会让你梦游到你所在道路的随机一端。因此，一分钟后，你有 $\frac{1}{2}$ 的概率到达道路的另一端，否则会回到原来的交叉路口。

不过有一点：你对每个单独的催眠兽有 $\frac{1}{2}$ 的概率免疫。如果你所在的道路上有一个你免疫的催眠兽，你总能在一分钟内安全地穿过这条路。如果你所在的道路上有一个你易感的催眠兽，你每次穿过这条路时都会睡着。你最初不知道哪些道路上有哪些催眠兽，但在尝试穿过某条道路后，你会知道你当前位于哪个端点。你到达 PokStop 的最小期望时间是多少？

输入格式

第一行包含两个整数 $n, m$ ($2 \le n \le 200\,000, 1 \le m \le 200\,000$)，分别表示城市中交叉路口的数量和连接它们的双向道路数量。接下来的 $m$ 行，每行包含两个整数 $a, b$ ($1 \le a, b \le n, a \neq b$)，表示由该道路连接的交叉路口编号。

没有两条交叉路口由多条道路连接。城市是连通的，即你可以通过多条道路从任何其他交叉路口到达任意交叉路口。

输出格式

输出一个实数，表示到达位于第 $n$ 个交叉路口的 PokStop 所需的最小期望时间。如果你的答案的绝对误差或相对误差不超过 $10^{-9}$，则被视为正确。

样例

输入格式 1

3 3
1 2
1 3
2 3

输出格式 1

1.500000000000

说明

在第一个样例测试中，最优策略是反复尝试直接通过第二条道路前往目的地。你有 $\frac{1}{2}$ 的概率对该道路上的催眠兽免疫，从而在时间 $1$ 内到达目的地。另一方面，你有 $\frac{1}{2}$ 的概率易感，我们可以证明在这种情况下，你到达目的地的期望时间为 $2 = \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \frac{1}{16} \cdot 4 + \dots$。因此，总的期望时间为 $\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 = \frac{3}{2}$。

输入格式 2

4 4
1 2
2 4
4 3
3 1

输出格式 2

2.875000000000

说明

在第二个样例测试中，如果你反复尝试通过第二个交叉路口，你的期望时间将等于 $3$ 分钟。如果你只尝试通过第三个交叉路口，结果也是一样。存在一种策略可以获得更好的期望时间。

以下是两个样例测试的示意图：