#P1417. Pku3156 Interconnect

Pku3156 Interconnect

Description

给出无向图G(V,E).每次操作任意加一条非自环的边(u,v),每条边的选择是等概率的.问使得G连通的期望操作次数.

(|V|<=30,|E|<=1000)

Input

第一行两个整数N,M 1<=N<=30 0<=M<=1000

接下来M行,每行两个整数X,Y表示两者之间已修好一条道路.

两点之间可以不止修了一条路,也有可能M条路已使N个点成为一个整体.

Output

输出一个小数,表示新修道路条数的期望值,保留六位小数.

Samples

4 2
1 2
3 4
1.500000