Problem6190--NOI2013湖北省选 二试 第2题 游走

6190: NOI2013湖北省选 二试 第2题 游走

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 512 MB

Submit

Description

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

Input

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

Output

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


【输入输出样例】
input        output
3 3             3.333
2 3
1 2
1 3

Sample Input Copy

3 3
2 3
1 2
1 3

Sample Output Copy

3.333

Source/Category