设
\[f(x) \]表示期望从 \(x\) 点离开的次数，
\[Num_e(x) \]表示 \(x\) 点的出度，
则每条边期望被经过的次数为
推dp柿子:
\[{f(x)=\sum_{v\in edge(x)} \frac{f(v)}{Num_e(v)}}\;,\;x \in (1,n). \] \[{f(x)=\sum_{v\in edge(x)} \frac{f(v)}{Num_e(v)}+1}\;,\;x=1. \] \[{f(x)=0\;,\;x=n.} \]第一个柿子是说，对于 \((1,n)\) 这些点，进入它们后必然出去一次，所以 \(E(into\;\;x)=E(out\;of\;\;x)\).
第二个柿子，对于 \(1\) 号点，从它出发决定了它离开次数比进入次数大 \(1\).
第三个柿子，\(n\) 为终点，不会再离开了.
然后大力高斯消元，把边按期望经过次数排序，贪心选择.
code:
#include <bits/stdc++.h>
#define ri register int
#define g() getchar()
#define MAXN 502
#define pc(a) putchar(a)
#define Tp template<typename T>
using namespace std;
namespace SlowIO
{
Tp inline void rd(T &x) {
x=0;char i=g();bool f=1;
while(!isdigit(i)) f&=(i!='-'),i=g();
while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
x*=((f<<1)-1);
}
Tp inline void op(T x){
if(x<0) pc('-'),x=-x;
if(x>=10) op(x/10);
pc(x%10+48);
}
Tp inline void writeln(T x){op(x);pc('\n');}
Tp inline void writesp(T x){op(x);pc(' ');}
};
using namespace SlowIO;
int cntr,head[MAXN];
struct edge{
int to,next;
}e[MAXN*MAXN];
inline void add(int u,int v){
e[++cntr].to=v;
e[cntr].next=head[u];
head[u]=cntr;
}
int n,m;
int deg[MAXN];//每个点的出度
double a[MAXN][MAXN];
double f[MAXN];//期望从x点离开的次数 E(离开x)
double g[MAXN*MAXN];
double ass;//Asswer
//x∈(1,n),f[x]=E(进入x点);
//f[1]=E(进入1点)+1,f[n]=0.
//Gauss-Jordan
#define abs fabs
inline bool solve()
{
ri sta;
for(ri i=1;i<=n;i++)
{
sta=i;
for(ri j=i+1;j<=n;j++)
if(abs(a[j][i])>abs(a[sta][i]))
sta=j;
if(sta!=i)
for(ri j=1;j<=n+1;j++)
swap(a[sta][j],a[i][j]);
if(!a[i][i]) return true;
for(ri j=1;j<=n;j++)
{
if(j==i) continue;
for(ri k=i+1;k<=n+1;k++)
a[j][k]-=a[i][k]*a[j][i]/a[i][i];
}
}
return false;
}
int main()
{
rd(n),rd(m);
static int u[MAXN*MAXN],v[MAXN*MAXN];
//我焯 我为什么一直开的MAXN啊我sb吗()
static int frm,tp;
for(ri i=1;i<=m;i++)
{
rd(u[i]),rd(v[i]);
add(u[i],v[i]),add(v[i],u[i]);
deg[u[i]]++,deg[v[i]]++;
}
//我焯 真就遍历所有边呗 O(2m)>O(m)(暴论)
a[1][n]=1;
for(ri i=1;i<=n-1;i++)
{
a[i][i]=1.0;
for(ri j=head[i];j;j=e[j].next)
{
int v=e[j].to;
if(v==n) continue;
a[i][v]=-1.0/deg[v];
}
}--n;solve();
for(int i=1;i<=n;i++) f[i]=a[i][n+1]/a[i][i];
for(ri i=1;i<=m;i++){
frm=u[i],tp=v[i];
g[i]+=(frm!=n+1)*f[frm]/deg[frm]+(tp!=n+1)*f[tp]/deg[tp];
}
sort(g+1,g+m+1);
for(ri i=1;i<=m;i++) ass+=1.0*i*g[m-i+1];
printf("%.3lf",ass);
return 0;
}