#2383. 「HNOI2013」游走

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

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

输入格式

输入第一行是正整数 N M ,分别表示该图的顶点数和边数,接下来 M 行每行是整数 u , v ( 1 \le u,v \le N ),表示顶点 u 与顶点 v 之间存在一条边。

输出格式

输出仅包含一个实数,表示最小的期望值,保留 3 位小数。

样例

样例输入

3 3 
2 3
1 2
1 3

样例输出

3.333

数据范围与提示

对于 30\% 的数据, N \le 10
对于 100\% 的数据, 2 \le N \le 500
输入数据保证是一个无向简单连通图。

数据根据 cyand1317 的 std 重制。