题目描述

给定无向连通图 $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\%$ 的数据，无特殊限制。