#P18824. [Croatian CPC2017] Kaktus

[Croatian CPC2017] Kaktus

[Croatian CPC2017] Kaktus

题目描述

仙人掌图是一种连通无向图,其中任意两个简单环至多有一个公共顶点。简单环指除起点与终点重合外,不重复经过顶点的环。

在给定的仙人掌图上进行以下随机过程:每一步从所有剩余的边中等概率选择一条并删除,各步使用独立的随机选择。图第一次变得不连通时,过程立即结束。也就是说,此时存在两个顶点,彼此之间没有任何路径。

求过程结束时执行步数的期望值。使图首次不连通的最后一次删除也计入步数。

输入格式

第一行包含两个整数 n,mn,m(1≤n≤6001\le n\le600,1≤m≤n(n−1)/21\le m\le n(n-1)/2),表示顶点数和边数。顶点编号为 11 至 nn。

接下来 mm 行,每行包含两个不同的整数 a,ba,b(1≤a,b≤n1\le a,b\le n),表示一条无向边。

保证没有重边,且给定图是上述定义的仙人掌图。

输出格式

输出一个实数,表示所求期望。

答案与标准答案的绝对误差或相对误差不超过 10−610^{-6} 即视为正确。

样例 1

输入

4 4
1 2
2 3
3 1
1 4

输出

1.75

样例 2

输入

12 14
1 2
2 3
3 1
2 4
4 5
6 5
3 7
7 8
8 9
9 10
10 7
8 11
8 12
11 12

输出

2.17582418

样例示意图

样例 1:

样例1

样例 2:

样例2