AT_arc153_f [ARC153F] Tri-Colored Paths

[problemUrl]: https://atcoder.jp/contests/arc153/tasks/arc153_f $ 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 $ で割った余りを出力してください．

### 制約 - $ 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 $ つ以下しか含まないので，条件を満たす塗り方は存在しません．