Home

Contest: Task: Related: TaskE TaskG

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$.