Description
傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。
幻想乡一共有 (n) 个地方，那么最快的方法当然是修复 (n-1) 条道路将这 (n) 个地方都连接起来。 幻想乡这 (n) 个地方本来是连通的，一共有 (m) 条边。现在这 (m) 条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第 (i) 条边所需要的时间为 (ei) 。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个 (ei) 会是一个0到1之间均匀分布的随机实数。并且所有 (ei) 都是完全独立的。
现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那 (n-1) 条边，同时开始修复，那么修复完成的时间就是这 (n-1) 条边的 (ei) 的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 (ei) 的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？
Input
第一行两个数 (n) ,(m)，表示地方的数量和边的数量。其中点从1到 (n) 标号。 接下来 (m) 行，每行两个数 (a),(b)，表示点 (a) 和点 (b) 之间原来有一条边。 这个图不会有重边和自环。
Output
一行输出答案，四舍五入保留6位小数。
Sample Input
5 4
1 2
1 5
4 3
5 3
Sample Output
0.800000
HINT
（以下内容与题意无关，对于解题也不是必要的。）
对于 (n) 个[0,1]之间的随机变量 (x1,x2,...,xn) ，第 (k) 小的那个的期望值是 (k/(n+1)) 。
样例解释：
对于第一个样例，由于只有4条边，幽香显然只能选择这4条，那么答案就是4条边的 (ei) 中最大的数的期望，由提示中的内容，可知答案为0.8。
数据范围：
对于所有数据：(nleq 10), (mleq n(n-1)/2),$ n,mgeq 1$。
对于15%的数据：(n leq 3)。
另有15%的数据：(nleq10, m=n)。
另有10%的数据：(nleq 10, m=n(n-1)/2)。
另有20%的数据：(nleq5)。
另有20%的数据：(n leq8)。
想法
第一眼看题，呀呀呀条件这么少咋算期望啊！
第二眼看到了提示，(emmm…) （还是不会#捂脸#）
首先，如果我们知道 (ei) 的确切值，就可以把 (ei) 从小到大排序然后 (kruskal) ，恰构成最小生成树是加入的最后一条边边权即为答案。
这就得到一种暴力方法：枚举出所有边的相对大小，一次次跑 (kruskal) 后算平均。
接着考虑如何优化。
假设 (kruskal) 求最小生成树时加的最后一条边为第 (i) 小的，那么它对答案的贡献为 (P(i) imes frac{i}{m+1}) ，(P(i)) 表示加上这个边后恰构成最小生成树的概率。
那么 (ans=sumlimits_{i=1}^{m} P(i) imes frac{i}{m+1}=frac{1}{m+1}sumlimits_{i=1}^{m} P(i) imes i)
而 (P(i) imes i) 可以理解为 (P(i)) 被加了 (i) 次
则 (ans=frac{1}{m+1}sumlimits_{i=1}^{m} sumlimits_{j=i}^{m} P(j))
我们再看后面这个东西 (sumlimits_{j=i}^{m} P(j)) ，意义是用 (i-1) 条边无法形成生成树（即，无法使图联通）的概率，设其为 (P'(i-1))。
显然，(P'(i)=frac{选i条边无法使图联通的方案数}{C_{m}^{i}})
于是，我们要求选 (i) 条边无法使原图联通的方案数
观察到 (n) 极小无比，我们考虑枚举子集的状压 (dp)
设 (f[i][j][0/1]) 表示在点集 (i) 中，选了 (j) 条边，该点集不连通/联通的方案数
求 (f[i][j][0]) 时用到一个小技巧：
将点集 (i) 分为互不联通的两个点集，令其中一个点集联通，另一个点集无所谓，保证这是一种符合要求的方案。
于是！！！找一个在点集 (i) 中的点 (t) , 枚举包含 (t) 的 (i) 的子集 (k) ，选若干条边使 (k) 联通，在点集 (i-k) 的生成子图中选剩下的边。
设 (size[i]) 表示 点集 (i) 的生成子图中的边数。
那么状态转移方程为：
(f[i][j][0]=sumlimits_{tin k subset i} sumlimits_{s=0}^{max(size[k],j)} f[k][s][1] imes C_{size[i^k]}^{j-s})
由于我们知道 (f[i][j][0]+f[i][j][1]=C_{size[i]}^{j})，在我们求出 (f[i][j][0]) 后可求 (f[i][j][1]=C_{size[i]}^{j}-f[i][j][0])
最后，(ans=frac{1}{m+1}sumlimits_{i=1}^{m} frac{f[全集][i-1][0]}{C_{m}^{i}})
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 2048;
typedef long long ll;
int n,m,w;
int size[N],u[100],v[100];
ll f[N][100][2],c[100][100];
int main()
{
n=read(); m=read();
for(int i=0;i<m;i++) u[i]=read(),v[i]=read();
w=(1<<n)-1;
for(int i=1;i<=w;i++)
for(int j=0;j<m;j++)
if((i&(1<<(u[j]-1))) && (i&(1<<(v[j]-1)))) size[i]++;
c[0][0]=1;
for(int i=1;i<=m;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
for(int i=1;i<=w;i++){
int t=i&(-i); //注意！这里不要轻易给f[i][0][0]与f[i][0][1]赋初值！！！
for(int j=0;j<=size[i];j++){
for(int k=(i-1)&i;k;k=(k-1)&i){
if(!(k&t)) continue;
for(int l=0;l<=j && l<=size[k];l++)
f[i][j][0]+=f[k][l][1]*c[size[i^k]][j-l];
}
f[i][j][1]=c[size[i]][j]-f[i][j][0];
}
}
double ans=0;
for(int i=0;i<m;i++) ans+=1.0*f[w][i][0]/(double)c[m][i];
printf("%.6lf
",ans/(m+1.0));
return 0;
}