生成树计数

题目描述

给定一张有 $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$ 取模的结果。

数据范围

对于 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$。

样例

输入样例 1

7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4

输出样例 1

12

输入样例 2

5 4
1 2
1 3
2 4
2 5

输出样例 2

1

样例解释

样例 1 的图由两个环（三角形与四边形）通过公共顶点 $3$ 连接，任意生成树都要在三角形里删掉一条边、在四边形里删掉一条边，共 $3 \times 4 = 12$ 棵。