3750 . [模板題] Counting Spanning Trees (Undirected)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

BaoCoder613

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

library-checker template

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$.

Input Format

$N$ $M$
$u_ 0$ $v_ 0$
$u_ 1$ $v_ 1$
$u_ 2$ $v_ 2$
$\vdots$
$u_ {M-1}$ $v_ {M-1}$

Output Format

Sample Input 1

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

Sample Output 1

8

Sample Input 2

1 2
0 0
0 0

Sample Output 2

1

Sample Input 3

4 4
0 1
1 0
2 3
3 2

Sample Output 3

0

Sample Input 4

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

Sample Output 4

26

Hints

  • $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$

Problem Source

library checker: counting_spanning_tree_undirected

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
17 5000 2097152 2097152
18 5000 2097152 2097152
19 5000 2097152 2097152
20 5000 2097152 2097152
21 5000 2097152 2097152
Submit
Back to Top