AT_arc105_f [ARC105F] Lights Out on Connected Graph

[problemUrl]: https://atcoder.jp/contests/arc105/tasks/arc105_f $ 1 $ から $ N $ の番号がついた $ N $ 個の頂点と、$ 1 $ から $ M $ の番号がついた $ M $ 本の辺からなる無向グラフ $ G $ が与えられます。$ G $ は連結で、自己ループや多重辺が存在しないことが保証されます。 辺 $ i $ は頂点 $ a_i $ と頂点 $ b_i $ を双方向につなぐ辺です。 それぞれの辺は赤か青のどちらかの色で塗ることができます。はじめ、全ての辺は赤で塗られています。 $ G $ から $ 0 $ 本以上の辺を取り除き新しいグラフ $ G^{\prime} $ を作ることを考えます。 $ G^{\prime} $ としてありうるグラフは $ 2^M $ 通りありますが、これらのうちよいグラフ(後述)であるようなものの個数を $ 998244353 $ で割ったあまりを求めてください。 $ G^{\prime} $ が以下の条件の両方を満たすとき、$ G^{\prime} $ は *よいグラフ* であるといいます。 - $ G^{\prime} $ は連結 - 以下の操作を $ 0 $ 回以上繰り返すことで、全ての辺の色を青色にできる - 頂点を $ 1 $ つ選び、その頂点に接続する全ての辺の色を変化させる。すなわち、辺の色が赤ならば青へ、青ならば赤へ変化させる。

N/A

N/A

### 制約 - 与えられる入力は全て整数 - $ 1\ \leq\ N\ \leq\ 17 $ - $ N-1\ \leq\ M\ \leq\ N(N-1)/2 $ - $ G $ は連結で、自己ループや多重辺が存在しない ### Sample Explanation 1 \- 辺 $ 1 $、辺 $ 2 $ のどちらも取り除かない場合のみ条件を満たします。 - 例えば、頂点 $ 2 $ に対して操作を行うことで、全ての辺を青色にすることが可能です。 - それ以外の場合はグラフが非連結になるため、条件を満たしません。 ### Sample Explanation 3 \- $ 998244353 $ で割ったあまりを求めるのを忘れずに。