题目描述

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

请计算将 $G$ 的每条边染成颜色 $1$、$2$ 或 $3$ 的方案数，要求满足以下条件，并将答案对 $998244353$ 取模：

• 存在一条 $G$ 的简单路径，且该路径上同时包含颜色 $1$、颜色 $2$、颜色 $3$ 的边。

简单路径指的是由顶点序列 $(v_1, \ldots, v_{k+1})$ 和边序列 $(e_1, \ldots, e_k)$ 组成的路径，满足以下条件：

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

输入格式

输入通过标准输入给出，格式如下：

$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

输出

0

样例 2

输入

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

输出

534

样例 3

输入

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

输出

144

样例 4

输入

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

输出

1794

说明/提示

限制条件

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

样例解释 1

$G$ 的所有简单路径都只包含至多 $2$ 条边，因此不存在满足条件的染色方案。

由 ChatGPT 4.1 翻译