#P18824. [Croatian CPC2017] Kaktus
[Croatian CPC2017] Kaktus
[Croatian CPC2017] Kaktus
题目描述
仙人掌图是一种连通无向图,其中任意两个简单环至多有一个公共顶点。简单环指除起点与终点重合外,不重复经过顶点的环。
在给定的仙人掌图上进行以下随机过程:每一步从所有剩余的边中等概率选择一条并删除,各步使用独立的随机选择。图第一次变得不连通时,过程立即结束。也就是说,此时存在两个顶点,彼此之间没有任何路径。
求过程结束时执行步数的期望值。使图首次不连通的最后一次删除也计入步数。
输入格式
第一行包含两个整数 (,),表示顶点数和边数。顶点编号为 至 。
接下来 行,每行包含两个不同的整数 (),表示一条无向边。
保证没有重边,且给定图是上述定义的仙人掌图。
输出格式
输出一个实数,表示所求期望。
答案与标准答案的绝对误差或相对误差不超过 即视为正确。
样例 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:

样例 2:
