配点 : $900$ 点

問題文

$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$ つ選び、その頂点に接続する全ての辺の色を変化させる。すなわち、辺の色が赤ならば青へ、青ならば赤へ変化させる。
• 頂点を $1$ つ選び、その頂点に接続する全ての辺の色を変化させる。すなわち、辺の色が赤ならば青へ、青ならば赤へ変化させる。

制約

• 与えられる入力は全て整数
• $1 \leq N \leq 17$
• $N-1 \leq M \leq N(N-1)/2$
• $G$ は連結で、自己ループや多重辺が存在しない

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$a_1$ $b_1$

$\vdots$

$a_M$ $b_M$

出力

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

3 2
1 2
2 3

1

• 辺 $1$、辺 $2$ のどちらも取り除かない場合のみ条件を満たします。- 例えば、頂点 $2$ に対して操作を行うことで、全ての辺を青色にすることが可能です。
• 例えば、頂点 $2$ に対して操作を行うことで、全ての辺を青色にすることが可能です。
• それ以外の場合はグラフが非連結になるため、条件を満たしません。

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

• $998244353$ で割ったあまりを求めるのを忘れずに。