F - Lights Out on Connected Graph 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 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 \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 で割ったあまりを出力せよ。

入力例 1

3 2
1 2
2 3

出力例 1

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

入力例 2

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

出力例 2

19

入力例 3

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

出力例 3

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

Score : 900 points

Problem Statement

Given is an undirected graph G consisting of N vertices numbered 1 through N and M edges numbered 1 through M. It is guaranteed that G is connected and contains no self-loops and no multi-edges. Edge i connects Vertex a_i and Vertex b_i bidirectionally. Each edge can be painted red or blue. Initially, every edge is painted red.

Consider making a new graph G^{\prime} by removing zero or more edges from G. There are 2^M graphs that G^{\prime} can be. Among them, find the number of good graphs defined below, modulo 998244353.

G^{\prime} is said to be a good graph when both of the following conditions are satisfied:

  • G^{\prime} is connected.
  • It is possible to make all edges blue by doing the following operation zero or more times.
    • Choose one vertex and change the color of every edge incident to that vertex, that is, red to blue and vice versa.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 17
  • N-1 \leq M \leq N(N-1)/2
  • G is connected and has no self-loops and no multi-edges.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M

Output

Print the number of good graphs among the ones that G^{\prime} can be, modulo 998244353.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1
  • The conditions are satisfied only if neither Edge 1 nor Edge 2 is removed.
    • In this case, we can make all edges blue by, for example, doing the operation for Vertex 2.
  • Otherwise, the graph gets disconnected and thus does not satisfy the condition.

Sample Input 2

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

Sample Output 2

19

Sample Input 3

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

Sample Output 3

90625632
  • Be sure to find the count modulo 998244353.