一个无向连通图，顶点从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 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=505;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 struct edge{17     int x,y;18 }e[mxn*mxn];19 int n,m;20 double ans=0;21 double f[mxn][mxn];22 void Gauss(){23     int i,j,k;24     for(i=1;i<=n;i++){25         int p=i;26         for(j=i+1;j<=n;j++)if(fabs(f[j][i])>fabs(f[p][i]))p=j;27         if(p!=i)28             for(j=i;j<=n+1;j++)swap(f[p][j],f[i][j]);29         for(j=i+1;j<=n;j++){30             double x=f[j][i]/f[i][i];31             for(k=i;k<=n+1;k++){32                 f[j][k]-=f[i][k]*x;33             }34         }35     }36     for(i=n;i;i--){37         for(j=i+1;j<=n;j++)38             f[i][n+1]-=f[i][j]*f[j][n+1];39         f[i][n+1]/=f[i][i]; 40 //        printf("i:%.3f\n",f[i][n+1]);41     }42     return;43 }44 double k[mxn][mxn];//点到点转移的概率 45 double g[mxn*mxn];//边被使用的期望次数 46 int out[mxn];//出度47 int cmp(double a,double b){return a>b;}48 int main(){49     int i,j,u,v;50     n=read();m=read();51     for(i=1;i<=m;i++){52         u=read();v=read();53         e[i].x=u;e[i].y=v;54         ++out[v];++out[u];55     }56     for(i=1;i<=m;i++){57         k[e[i].x][e[i].y]+=(double)1/out[e[i].x];58         k[e[i].y][e[i].x]+=(double)1/out[e[i].y];59     }60     f[1][n+1]=-1;f[n][n]=1;f[n][n+1]=0;61     for(i=1;i<n;i++){62         for(j=1;j<=n;j++){63             f[i][j]=k[j][i];64         }65         f[i][i]-=1;66     }67 /*    for(i=1;i<=n;i++){68         for(j=1;j<=n+1;j++)69             printf("%.3f  ",f[i][j]);70         printf("\n");71     }*/72     Gauss();73     for(i=1;i<=m;i++){74         g[i]=f[e[i].x][n+1]/out[e[i].x]+f[e[i].y][n+1]/out[e[i].y];75     }76     sort(g+1,g+m+1,cmp);77     for(i=1;i<=m;i++)ans+=g[i]*i;78     printf("%.3f\n",ans);79     return 0;80 }