Pku3156 Interconnect

给定一个无向图 $G=(V,E)$。每次操作时，从所有端点不同的无序顶点对 $(u,v)$ 中等概率地选择一对，并在 $u$ 与 $v$ 之间加入一条边。图中允许存在重边，但不允许加入自环。

求使图 $G$ 连通所需操作次数的期望值。初始图可能已经连通。

输入格式

第一行包含两个整数 $N,M$，分别表示顶点数和初始边数。

接下来 $M$ 行，每行包含两个整数 $X,Y$，表示顶点 $X$ 与顶点 $Y$ 之间已有一条边。

两个顶点之间可能存在多条边。

输出格式

输出一个实数，表示使图连通所需新增边数的期望值，保留 $6$ 位小数。

样例输入

4 2
1 2
3 4

样例输出

1.500000

数据范围

• $1\le N\le 30$；
• $0\le M\le 1000$；
• 初始的 $M$ 条边可能已经使整个图连通。

来源与许可

本题题面与测试数据整理自 BZOJ 1417（PKU 3156 Interconnect）。

样例 1

输入

4 2
1 2
3 4

输出

1.500000