

Time Limit: 3 sec / Memory Limit: 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.