无向图生成树计数

【题目描述】

给定一张由 $N$ 个顶点和 $M$ 条边构成的无向图。第 $i$ 条边连接顶点 $u_i$ 与 $v_i$。这张图不一定是简单图。

求该图的生成树个数，答案对 $998244353$ 取模。

【输入】

$N$ $M$
$u_0$ $v_0$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{M-1}$ $v_{M-1}$

【输出】

输出该图生成树个数对 $998244353$ 取模的结果。

【输入样例】

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

【输出样例】

8

【输入样例2】

1 2
0 0
0 0

【输出样例2】

1

【输入样例3】

4 4
0 1
1 0
2 3
3 2

【输出样例3】

0

【输入样例4】

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

【输出样例4】

26

【数据范围】

• $1 \leq N \leq 500$
• $0 \leq M \leq 500000$
• $0 \leq u_i \lt N$
• $0 \leq v_i \lt N$

【来源】

Library Checker（yosupo06） counting_spanning_tree_undirected