AT_fps_24_w 閉路

頂点に $ 1 $ から $ N $ までの番号がついた $ N $ 頂点 $ M $ 辺の単純無向グラフ $ G $ が与えられます。 $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 $ G $ の全域部分グラフ(全ての頂点を含む部分グラフ)のうち、次の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - 頂点 $ 1 $ と頂点 $ N $ がともに含まれる閉路が存在する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

$ G $ の全域部分グラフのうち、条件を満たすものの個数を $ 998244353 $ で割った余りを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ N \leq 10 $ を満たすデータセットに正解した場合、 $ 4 $ 点が与えられる。 ### Sample Explanation 1 例えば辺集合が $ 1 $ 番目の辺、 $ 2 $ 番目の辺、 $ 3 $ 番目の辺、 $ 5 $ 番目の辺からなる全域部分グラフは条件を満たします。なぜならば、 $ 2 $ 番目の辺、 $ 3 $ 番目の辺、 $ 5 $ 番目の辺が頂点 $ 1 $ と頂点 $ 4 $ がともに含まれる閉路をなすからです。 ### Constraints - $ 3 \leq N \leq 16 $ - $ 3 \leq M \leq \binom{N}{2} $ - $ 1 \leq A_i \lt B_i \leq N $ - $ i \neq j $ ならば $ (A_i, B_i) \neq (A_j, B_j) $ - 入力される値は全て整数