#P18584. Graph Completing

Graph Completing

Graph Completing

给定一张有 nn 个顶点、mm 条边的简单连通无向图。你可以在原本没有边的顶点对之间添加边,也可以一条边都不添加。最终图仍须是简单图。

求使最终图边双连通的补边方案数,对 998244353998244353 取模。两个方案不同,当且仅当它们所添加的边集不同。

这里,边双连通表示任意两个不同顶点之间都有两条不共用任何边的路径;等价地,删除最终图的任意一条边后,图仍然连通。路径可以共用中间顶点。

原题的三种图结构

上图取自原题 PDF:左图不连通;中图连通但存在桥;右图边双连通。

输入格式

第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含两个整数 ui,viu_i,v_i,表示一条无向边。顶点编号为 11 到 nn。

保证原图连通,无自环、无重边。输入只包含一组数据。

输出格式

输出一个整数,表示补边方案数对 998244353998244353 取模的结果。

数据范围

2≤n≤50002\le n\le5000,n−1≤m≤min⁡ ⁣(n(n−1)2,10000)n-1\le m\le\min\!\left(\frac{n(n-1)}2,10000\right),1≤ui,vi≤n1\le u_i,v_i\le n。

样例输入 1

3 2
1 2
2 3

样例输出 1

1

样例输入 2

4 4
1 2
2 3
3 4
4 1

样例输出 2

4

样例说明

第一组只能补上边 (1,3)(1,3)。第二组原图已边双连通,缺少的两条对角线可以分别自由选择是否添加,因此有四种方案。