[AdditionalFile3323.zip](file://AdditionalFile3323.zip?type=additional_file)

#3323. 「SNOI2020」生成树

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

给定无向连通图 $G$，已知 $G$ 在删掉一条边后是一颗仙人掌（仙人掌：不存在两个拥有公共边的简单环的无向联通图），求 $G$ 的生成树个数。结果对 $998244353$ 取模。

输入格式

第一行两个整数 $n,m$，表示图 $G$ 的点数和边数。

接下来 $m$ 行，每行两个用空格分隔的正整数 $u, v(1\le u, v\le n)$，表示边 $(u,v)\in G$。

输出格式

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

样例

输入

4 5
1 2
1 3
2 3
2 4
3 4

输出

8

数据范围与提示

对于所有数据，$1\le n\le m\le 5\times 10^5$。

• 对于 $10\%$ 的数据，$1\le n=m\le 2000$。
• 对于另外 $40\%$ 的数据，$1\le n,m\le 10^5$ 且 $G$ 本身是仙人掌。
• 对于余下 $50\%$ 的数据，无特殊限制。