题目描述

给定一个由 $N$ 个顶点编号为 $1$ 到 $N$ 和 $M$ 条边编号为 $1$ 到 $M$ 的无向图 $G$。保证 $G$ 是连通的，且没有自环和多重边。第 $i$ 条边连接了顶点 $a_i$ 和顶点 $b_i$。每条边可以被涂成红色或蓝色。初始时，所有的边都是红色的。

通过从 $G$ 中移除 $0$ 条或更多边，创建一个新的图 $G^{\\prime}$。有 $2^M$ 种 $G^{\\prime}$ 可能的情况。在这些情况中，找到满足下述条件的 良好图 的数量，结果对 $998244353$ 取模。

当满足以下两个条件时，$G^{\\prime}$ 被称为 良好图 ：

• $G^{\\prime}$ 是连通的。
• 可以通过执行以下操作 $0$ 次或多次使所有边变成蓝色。
  • 选择一个顶点，将与该顶点相邻的每条边的颜色改变，即红色变成蓝色，蓝色变成红色。

约束条件

• 输入中的所有值都是整数。
• $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$

输出

打印满足条件的良好图的数量对 $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$。