U394197 果国的奇妙旅行

[NKOJ P9337](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2627&tid=V)

果国有 $n$ 座城市和 $m$ 条连接两座不同城市的双向道路 。 你从城市 $1$ 出发准备前往城市 $n$ 。 果国的道路漫长而危险，但你很有钱，计划全程坐车通行。 来到售票站时，你发现果国居然买个票也得看脸？ 具体来说，$i$ 号城市的售票站只会出售从 $i$ 号城市出发经过某条道路的单程车票。车票由系统等概率随机抽取，每座城市每次抽取所需费用均相同。 虽然你很有钱，但也不想花很多冤枉钱，因此得精打细算。经过一番计算，你发现，有些票扔掉也比坐过去划算（可能变得离目的地更远）。 最终你敲定计划： - 到达一个城市后立即买（抽）票 - 选择扔掉这张票，重新买票；或者使用这张票到达道路另一端的城市 - 到达城市 $n$ 后立即停止 你想知道，在**最优策略**下，从城市 $1$ 到达城市 $n$ 所需的期望购票数。

第一行输入 $n,m$。 接下来 $m$ 行，每行输入两个整数 $u,v$ 表示一条道路。

输出最优策略下，从 $1$ 到 $n$ 的期望购票数。 绝对误差需不超过 $10^{-6}$。

$1\leq n,m\leq3\times10^5$ 数据保证从 $1$ 出发能够到达 $n$ ，且图中不含重边和自环。 注：为全真模拟 NKOJ 的优秀性能，时限为 0.4s。 数据下载：[https://cqwdx.lanzouq.com/iXytm1jg8yod](https://cqwdx.lanzouq.com/iXytm1jg8yod)