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 ai​ and Vertex bi​ bidirectionally. Each edge can be painted red or blue. Initially, every edge is painted red.

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

G′ is said to be a good graph when both of the following conditions are satisfied:

• G′ 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\le N\le 17$
• $N-1\le M\le N(N-1)/2$
• $G$ is connected and has no self-loops and no multi-edges.

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