考虑一个包含 $n$ 个顶点的连通无向图。将该图称为初始图。

一个三元组 $(a, b, c)$（$1 \le a < b < c \le n$）被称为是好的，当且仅当：

• 顶点 $a$ 和 $b$ 之间有边相连。
• 顶点 $a$ 和 $c$ 之间有边相连。
• 顶点 $b$ 和 $c$ 之间没有边相连。

对初始图运行以下算法：只要存在好的三元组，就任选一个好的三元组 $(a, b, c)$，并在顶点 $b$ 和 $c$ 之间添加一条边。将最终得到的图称为完备图。可以证明，完备图不依赖于每次迭代中好三元组的选择。

给你一个初始图。完备图有多少种使用 $n$ 种颜色的染色方案？图的染色是指给顶点分配颜色，使得任意两个相邻的顶点颜色不同。如果需要更正式的定义，请参考问题 D。

输出正确答案模 $998244353$ 的值。正式地，如果真实答案是 $y$，而你的答案是 $x$，当 $-2^{63} \le x < 2^{63}$ 且 $x - y$ 能被 $998244353$ 整除时，你的答案将被视为正确。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$，$1 \le m \le 3 \cdot 10^5$），分别表示初始图中的顶点数和边数。

接下来的 $m$ 行包含初始图边的描述。第 $i$ 行包含两个整数 $u$ 和 $v$（$1 \le u < v \le n$），表示第 $i$ 条边的两个端点。

保证给定的图是连通的，且不包含重边。

输出格式

输出一个整数，表示完备图使用 $n$ 种颜色的染色方案数模 $998244353$ 的值。

样例

输入样例 1

3 2
1 2
1 3

输出样例 1

6

输入样例 2

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

输出样例 2

645120

说明

在第一个样例中，初始图如下所示：

唯一可能的好三元组是 $(1, 2, 3)$，因此完备图如下所示：

以下是该图使用 3 种颜色的全部 6 种染色方案：