[HNOI2013]游走
题号:NC20105
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

第一行是正整数N和M,分别表示该图的顶点数 和边数,接下来M行每行是整数u,v(1 ≤ u,v ≤ N),表示顶点u与顶点v之间存在一条边。
输入保证30%的数据满足N ≤ 10,100%的数据满足2 ≤ N ≤ 500且是一个无向简单连通图。

输出描述:

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

输入

复制
3  3                
2  3
1  2
1  3

输出

复制
3.333

说明

边 (1,2)编号为1,边 (1,3)编号2,边 (2,3)编号为3。

备注:

对于30%的数据,保证 
对于100%的数据,保证 ,给出的图无重边和自环,且从1出发可以到达所有的节点。