题目描述

$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$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$

输出格式

$G^{\prime}$ としてありうるグラフのうち、よいグラフであるものの個数を $998244353$ で割ったあまりを出力せよ。

题目大意

题意

有一张 $n$ 个点 $m$ 条边的简单无向图，问选出一个边集，使得 $n$ 个点与这些边构成的图连通，并且图是二分图的方案数。

对 $998244353$ 取模。

$1\leq n\leq 17,n-1\leq m\leq \frac{n(n-1)}{2}$。

3 2
1 2
2 3

1

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

19

17 50
16 17
10 9
16 10
5 17
6 15
5 9
15 11
16 1
8 13
6 17
15 3
16 15
11 3
7 6
1 4
11 13
10 6
10 12
3 16
7 3
16 5
13 3
12 13
7 11
3 12
13 10
1 12
9 15
11 14
4 6
13 2
6 1
15 2
1 14
15 17
2 11
14 13
16 9
16 8
8 17
17 12
1 11
6 12
17 2
8 1
14 6
9 7
11 10
5 14
17 7

90625632

提示

制約

• 与えられる入力は全て整数
• $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$ で割ったあまりを求めるのを忘れずに。