数学期望/高斯消元/贪心
啊……用贪心的思路明显是要把经过次数期望越大的边的权值定的越小，那么接下来的任务就是求每条边的期望经过次数。
拆边为点？nonono，连接x,y两点的边的期望经过次数明显是 times[x]/du[x]+times[y]/du[y] 所以只要求出每个点的期望经过次数即可
像「随机程序」那道题一样，（马尔可夫过程？）高斯消元求解即可
特别的，第1个点是起点，方程组的常数项为1，而 「第N个点是终点，期望经过次数为0，不参与消元」 （因为走到N就停下了，不会“经过”）（这个地方WA了……sigh）
/**************************************************************
Problem: 3143
User: Tunix
Language: C++
Result: Accepted
Time:3716 ms
Memory:8284 kb
****************************************************************/ //BZOJ 3143
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*=sign;
}
const int N=,M=;
const double eps=1e-;
typedef double Matrix[N][N];
/******************tamplate*********************/
void gauss_jordan(Matrix A,int n){
int r;
rep(i,n){
r=i;
for(int j=i+;j<n;j++)
if (fabs(A[j][i]) > fabs(A[r][i])) r=j;
if (fabs(A[r][i]) < eps) continue;
if (r!=i) F(j,,n) swap(A[r][j],A[i][j]);
rep(k,n) if (k!=i)
D(j,n,i) A[k][j]-=A[k][i]/A[i][i]*A[i][j];
}
} Matrix A;
int n,m,d[N],u[M],v[M];
double w[M],x[N];
vector<int>G[N]; int main(){
#ifndef ONLINE_JUDGE
freopen("3143.in","r",stdin);
freopen("3143.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,m){
u[i]=getint()-; v[i]=getint()-;
G[u[i]].pb(v[i]); G[v[i]].pb(u[i]);
}
rep(i,n) d[i]=G[i].size();
memset(A,,sizeof (A));
rep(i,n-){
A[i][i]=;
rep(j,G[i].size())
A[i][G[i][j]]=-1.0/d[G[i][j]];
if (i==) A[i][n]=1.0;
} gauss_jordan(A,n);
rep(i,n) x[i]=A[i][n]/A[i][i];
x[n-]=;
F(i,,m) w[i]=x[u[i]]/d[u[i]]+x[v[i]]/d[v[i]];
sort(w+,w+m+);
double ans=0.0;
F(i,,m) ans+=w[m-i+]*i;
printf("%.3lf\n",ans);
return ;
}