11267: [yosupo] Graph - Counting Spanning Trees (Undirected)
[Creator : ]
Description
You are given an undirected graph, consisting of $N$ vertices and $M$ edges. The $i$-th edge connects vertex $u_i$ and $v_i$. This graph may not be simple.
Find the number of spanning trees of the graph modulo $998244353$.
Find the number of spanning trees of the graph modulo $998244353$.
Input
$N$ $M$
$u_0$ $v_0$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$u_0$ $v_0$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{M-1}$ $v_{M-1}$
Constraints
- $1 \leq N \leq 500$
- $0 \leq M \leq 5\times 10^5$
- $0 \leq u_i \lt N$
- $0 \leq v_i \lt N$
- $0 \leq M \leq 5\times 10^5$
- $0 \leq u_i \lt N$
- $0 \leq v_i \lt N$
Sample 1 Input
3 5
0 1
0 1
1 2
2 1
2 0
Sample 1 Output
8
Sample 2 Input
1 2
0 0
0 0
Sample 2 Output
1
Sample 3 Input
4 4
0 1
1 0
2 3
3 2
Sample 3 Output
0
4 8
0 1
0 3
2 1
3 1
3 0
3 0
2 3
1 3
26