题目描述

给定无向连通图 $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 \le2 \times 10^5$。

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