所以说我讨厌数学……期望不会高斯消元也不会……好不容易抄好了高斯消元板子被精度卡成琪露诺了……
首先，我们先算出走每一条边的期望次数，那么为了最小化期望，就让大的期望次数乘上小编号
边的期望次数是多少呢？可以先算出点的概率
$p(u,v)=\frac{p[u]}{d[u]}+\frac{p[v]}{d[v]}$
$p[u]$表示经过这个点的期望次数，$d[u]$表示这个点的度数
那么点的期望次数怎么求？
$p[u]=\sum_{(u,v)\in E}\frac{p[v]}{d[v]}$
然后发现这玩意儿会产生环，因为一个点的期望次数需要由它周围的点推出，他周围的点又需要它推出
那么我们考虑列方程，用高斯消元求解
代码如下
for(int i=;i<n;++i){
f[i][i]=1.0;
for(int j=head[i];j;j=Next[j])
if(ver[j]!=n)
f[i][ver[j]]=-/d[ver[j]];
}
f[][n]=;
其中$f[i][j]$表示从$j$转移到$i$的期望次数
这个方程实际上是$这个点的期望次数*1-所有相邻的点转移过来的期望次数=0$
然后因为一开始在第一个点，所以第一个点必定到，设为$f[1][n]=1$
//minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while((ch=getc())>''||ch<'')
(ch=='-')&&(flag=true);
for(res=num;(ch=getc())<=''&&ch>='';res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=;const double eps=1e-;
int ver[N*N*],Next[N*N*],from[N*N*],to[N*N*],head[N],tot,n,m;
double d[N],f[N][N],ans[N],sum,E[N*N*];
inline void add(int u,int v){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
void gauss(){
for(int i=;i<n;++i){
int k=i;
for(int j=i+;j<n;++j)
if(fabs(f[k][i])<fabs(f[j][i])) k=j;
if(k!=i) swap(f[i],f[k]);
double div=f[i][i];
for(int j=i;j<=n;++j) f[i][j]/=div;
for(int j=i+;j<n;++j){
double t=f[j][i];
for(int k=;k<n+;++k)
f[j][k]-=t*f[i][k];
}
}
for(int i=n-;i;--i){
for(int j=i+;j<n;++j)
f[i][n]-=f[i][j]*ans[j];
ans[i]=f[i][n]/f[i][i];
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read();
for(int i=,u,v;i<=m;++i){
u=read(),v=read();add(u,v),add(v,u);
d[u]+=,d[v]+=;
from[i]=u,to[i]=v;
}
for(int i=;i<n;++i){
f[i][i]=1.0;
for(int j=head[i];j;j=Next[j])
if(ver[j]!=n)
f[i][ver[j]]=-/d[ver[j]];
}
f[][n]=;
gauss();
for(int i=;i<=m;++i)
E[i]=ans[from[i]]/d[from[i]]+ans[to[i]]/d[to[i]];
sort(E+,E++m);
for(int i=;i<=m;++i) sum+=E[i]*(m-i+1.0);
printf("%.3lf\n",sum);
return ;
}