计数生成树（无向）

（Counting Spanning Trees (Undirected)）

问题描述

给定一个无向图（可能含重边和自环），含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

求该图的生成树数量（即边数为 $N-1$、连通且无环的子图个数），结果对 $998244353$ 取模。

约束条件

• $1 \leq N \leq 500$
• $0 \leq M \leq 5 \times 10^5$
• $0 \leq u_i, v_i < N$

输入

$N\ M$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{M-1}\ v_{M-1}$

输出

生成树数量 $\bmod\ 998244353$

3 5
0 1
0 1
1 2
2 1
2 0

8

1 2
0 0
0 0

1

#3

4 4
0 1
1 0
2 3
3 2

0

4 8
0 1
0 3
2 1
3 1
3 0
3 0
2 3
1 3

26