#P3232. [HNOI2013] 游走

[HNOI2013] 游走

题目描述

给定一个 nn 个点 mm 条边的无向连通图,顶点从 11 编号到 nn,边从 11 编号到 mm

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

输入格式

第一行是两个整数,分别表示该图的顶点数 nn 和边数 mm

接下来 mm 行每行两个整数 u,vu,v,表示顶点 uu 与顶点 vv 之间存在一条边。

输出格式

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

3 3
2 3
1 2
1 3
3.333

提示

样例输入输出 1 解释

(1,2)(1,2) 编号为 11,边 (1,3)(1,3) 编号 22,边 (2,3)(2,3) 编号为 33


数据规模与约定

  • 对于 30%30\% 的数据,保证 n10n\leq 10
  • 对于 100%100\% 的数据,保证 2n5002\leq n \leq 5001m1250001 \leq m \leq 1250001u,vn1 \leq u, v \leq n,给出的图无重边和自环,且从 11 出发可以到达所有的节点。