题目描述

$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$ で割った余りを出力してください．

题目大意

给出一张 $N$ 个点 $M$ 条边的简单无向连通图。

你可以将分别每一条边染为 $1,2,3$ 三种颜色之一。问不同的染色方案数，使得图中存在一条路径，其上同时存在三种颜色的边。答案对 $998244353$ 取模。

3 3
1 2
1 3
3 2

0

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

534

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

144

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$
• 与えられるグラフは連結かつ単純である

Sample Explanation 1

$G$ の単純パスはいずれも辺を $2$ つ以下しか含まないので，条件を満たす塗り方は存在しません．