06612. GESP-8级-2026-09-生成树计数

题目描述

给定一张有 $n$ 个顶点 $m$ 条边的无向连通图 $G$ ，顶点依次以 $1, 2, \dots, n$ 编号。 $G$ 有以下特殊的性质：

简单环是指环中顶点互不相同，且不经过重复边的回路。

请你求出 $G$ 的不同生成树的数量。两棵生成树不同，当且仅当存在一条边在其中一棵生成树中出现，而不在另一棵生成树中出现。

由于答案可能很大，你只要求出答案对 $998244353$ 取模的结果。

第一行，两个正整数 $n, m$ ，分别表示 $G$ 的顶点数与边数。

接下来 $m$ 行，每行两个整数 $u_{i}, v_{i}$ ，表示一条连接顶点 $u_{i}, v_{i}$ 的无向边。

输出一行，一个整数，表示 $G$ 的不同生成树的数量对 $998244353$ 取模的结果。

输入

输出

对于 $40%$ 的测试点，保证 $1 \leq n \leq 8$ ， $1 \leq m \leq 10$ 。

对于 $60%$ 的测试点，保证 $1 \leq n \leq 2000$ ， $1 \leq m \leq 2000$ 。

对于所有测试点，保证 $1 \leq n \leq 1 0^{5}$ ， $1 \leq m \leq 1 0^{5}$ ， $1 \leq u_{i}, v_{i} \leq n$ 。

来源：洛谷 P17461（CCF GESP 8 级上机题）