5614：[GESP202609八级] 生成树计数
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 题目背景
2026 年 09 月 GESP C++ 八级编程第 1 题
## 题目描述
给定一张有 $n$ 个顶点 $m$ 条边的无向连通图 $G$，顶点依次以 $1,2,\ldots,n$ 编号。$G$ 有以下特殊的性质：
- $G$ 中的每条边至多属于一个简单环。
- $G$ 中没有重边与自环。
简单环是指环中顶点互不相同，且不经过重复边的回路。
请你求出 $G$ 的不同生成树的数量。两棵生成树不同，当且仅当存在一条边在其中一棵生成树中出现，而不在另一棵生成树中出现。
由于答案可能很大，你只要求出答案对 $998244353$ 取模的结果。
## 输入格式
第一行，两个正整数 $n,m$，分别表示 $G$ 的顶点数与边数。
接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示一条连接顶点 $u_i,v_i$ 的无向边。
## 输出格式
输出一行，一个整数，表示 $G$ 的不同生成树的数量对 $998244353$ 取模的结果。
## 样例
```input1
7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
```
```output1
12
```
```input2
5 4
1 2
1 3
2 4
2 5
```
```output2
1
```
## 数据范围
对于 $40\%$ 的测试点，保证 $1\le n\le 8$，$1\le m\le 10$。
对于 $60\%$ 的测试点，保证 $1\le n\le 2000$，$1\le m\le 2000$。
对于所有测试点，保证 $1\le n\le 10^5$，$1\le m\le 10^5$，$1\le u_i,v_i\le n$。