一个无向连通图，顶点从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位小数。

#include <cstdio>#include <iostream>#include <cmath>#include <algorithm>using namespace std;const int V = 505;const int E = 250005;const double eps = 1e-8;struct edge{  int fro, nxt, to;}e[E << 1];int n, m;int fir[V], deg[V], cnt = 0;double M[V][V], sol[V], ex[E];inline void add(int x, int y) {  e[++ cnt].to = y;  e[cnt].fro = x;  e[cnt].nxt = fir[x];  fir[x] = cnt;}inline int sgn(double x) {  if (fabs(x) < eps) return 0;  if (x > 0) return 1;  return -1;}inline void Gauss() {  for (int i = 1; i <= n; i ++) {    for (int j = i; j <= n; j ++)      if (sgn(M[j][i])) {	swap(M[i], M[j]);	break;      }    if (!sgn(M[i][i])) return;    double tmp = 1.0 / M[i][i];    for (int j = i; j <= n + 1; j ++) M[i][j] *= tmp;    for (int j = i + 1; j <= n; j ++)      if (sgn(M[j][i])) {	tmp = M[j][i];	for (int l = i; l <= n + 1; l ++) M[j][l] -= M[i][l] * tmp;      }  }  for (int i = n; i >= 1; i --) {    for (int j = i + 1; j <= n; j ++)      M[i][n + 1] -= M[i][j] * sol[j];    sol[i] = M[i][n + 1];  }}inline bool cmp(double a, double b) {  return a > b;}int main() {  int x, y;  scanf("%d%d", &n, &m);  for (int i = 1; i <= m; i ++) {    scanf("%d%d", &x, &y);    add(x, y); add(y, x);    deg[x] ++; deg[y] ++;  }  for (int i = 1; i < n; i ++) {    M[i][i] = - 1.0;    for (int j = fir[i]; j; j = e[j].nxt)      M[i][e[j].to] += 1.0 / deg[e[j].to];  }  M[1][n + 1] = - 1.0;  M[n][n] = 1.0;  for (int i = 1; i <= n; i ++)    for (int j = 1; j <= n + 1; j ++) M[i][j] *= 100;  Gauss();  for (int i = 1; i <= m; i ++) {    x = e[i * 2].fro;    y = e[i * 2].to;    ex[i] = sol[x] * 1.0 / deg[x] + sol[y] * 1.0 / deg[y];  }  sort(ex + 1, ex + m + 1, cmp);  double ans = 0;  for (int i = 1; i <= m; i ++) ans += 1.0 * i * ex[i];  printf("%.3lf\n", ans);  return 0;}