[HNOI2013] 游走

题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图,顶点从 $1$ 编号到 $n$,边从 $1$ 编号到 $m$。 小 Z 在该图上进行随机游走,初始时小 Z 在 $1$ 号顶点,每一步小 Z 以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这 $m$ 条边进行编号,使得小 Z 获得的总分的期望值最小。

输入输出格式

输入格式


第一行是两个整数,分别表示该图的顶点数 $n$ 和边数 $m$。 接下来 $m$ 行每行两个整数 $u,v$,表示顶点 $u$ 与顶点 $v$ 之间存在一条边。

输出格式


输出一行一个实数表示答案,保留三位小数。

输入输出样例

输入样例 #1

3 3
2 3
1 2
1 3

输出样例 #1

3.333

说明

#### 样例输入输出 1 解释 边 $(1,2)$ 编号为 $1$,边 $(1,3)$ 编号 $2$,边 $(2,3)$ 编号为 $3$。 --- #### 数据规模与约定 - 对于 $30\%$ 的数据,保证 $n\leq 10$。 - 对于 $100\%$ 的数据,保证 $2\leq n \leq 500$, $1 \leq m \leq 125000$,$1 \leq u, v \leq n$,给出的图无重边和自环,且从 $1$ 出发可以到达所有的节点。