题目描述

给定一个简单连通无向图 $G$，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

找出对于 $G$ 中每条边涂上颜色 $1$、$2$ 或 $3$ 的方式的数量，使得满足以下条件，结果取模 $998244353$。

• 在 $G$ 中存在一条简单路径，其中包含一条颜色为 $1$ 的边、一条颜色为 $2$ 的边和一条颜色为 $3$ 的边。

什么是简单路径？简单路径是指满足以下条件的顶点序列 $(v_1, v_2, \\ldots, v_{k+1})$ 和边序列 $(e_1, e_2, \\ldots, e_k)$：

• $i\\neq j \\implies v_i\\neq v_j$；
• 边 $e_i$ 连接顶点 $v_i$ 和 $v_{i+1}$。

约束条件

• $3 \\leq N\\leq 2\\times 10^5$
• $3 \\leq M\\leq 2\\times 10^5$
• $1 \\leq A_i, B_i \\leq N$
• 给定的图是简单连通图。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $M$ $A_1$ $B_1$ $\\vdots$ $A_M$ $B_M$

输出

输出结果应以如下格式打印到标准输出：

打印对于 $G$ 中每条边涂上颜色 $1$、$2$ 或 $3$ 的方式的数量，使得满足题目中所描述的条件，结果取模 $998244353$。

示例输入 1

3 3
1 2
1 3
3 2

示例输出 1

0

$G$ 中的任意简单路径包含两条边或更少，因此无法满足条件。

示例输入 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

示例输出 2

534

示例输入 3

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

示例输出 3

144

示例输入 4

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

示例输出 4

1794