配点 : $1000$ 点

問題文

$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}$ を結ぶ．

## 制約 - $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$ で割った余りを出力してください． ```input1 3 3 1 2 1 3 3 2 ``` ```output1 0 ``` $G$ の単純パスはいずれも辺を $2$ つ以下しか含まないので，条件を満たす塗り方は存在しません． ```input2 4 6 1 2 1 3 1 4 2 3 2 4 3 4 ``` ```output2 534 ``` ```input3 6 5 1 3 4 3 5 4 4 2 1 6 ``` ```output3 144 ``` ```input4 6 7 1 2 2 3 3 1 4 5 5 6 6 4 1 6 ``` ```output4 1794 ```$$