[Hnoi2013]游走
时间限制：10s 空间限制：128MB
题目描述
一个无向连通图，顶点从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位小数。
样例输入
3 3 2 3 1 2 1 3
样例输出
3.333
提示
边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。
题目来源
非官方数据