#P18584. Graph Completing
Graph Completing
Graph Completing
给定一张有 个顶点、 条边的简单连通无向图。你可以在原本没有边的顶点对之间添加边,也可以一条边都不添加。最终图仍须是简单图。
求使最终图边双连通的补边方案数,对 取模。两个方案不同,当且仅当它们所添加的边集不同。
这里,边双连通表示任意两个不同顶点之间都有两条不共用任何边的路径;等价地,删除最终图的任意一条边后,图仍然连通。路径可以共用中间顶点。

上图取自原题 PDF:左图不连通;中图连通但存在桥;右图边双连通。
输入格式
第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示一条无向边。顶点编号为 到 。
保证原图连通,无自环、无重边。输入只包含一组数据。
输出格式
输出一个整数,表示补边方案数对 取模的结果。
数据范围
,,。
样例输入 1
3 2
1 2
2 3
样例输出 1
1
样例输入 2
4 4
1 2
2 3
3 4
4 1
样例输出 2
4
样例说明
第一组只能补上边 。第二组原图已边双连通,缺少的两条对角线可以分别自由选择是否添加,因此有四种方案。