题目描述

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

你可以从 $G$ 中删除 $0$ 条或多条边，得到一个新图 $G^{\prime}$。所有可能的 $G^{\prime}$ 有 $2^M$ 种。请计算其中满足下述条件的“好图”的个数，并对 $998244353$ 取模：

• $G^{\prime}$ 是连通图。
• 可以通过若干次如下操作（可以为 $0$ 次），将所有边的颜色变为蓝色：
  • 选择一个顶点，将与该顶点相连的所有边的颜色反转（红变蓝，蓝变红）。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$

输出格式

输出所有可能的 $G^{\prime}$ 中“好图”的个数对 $998244353$ 取模的结果。

样例 1

输入

3 2
1 2
2 3

输出

1

样例 2

输入

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

输出

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

输出

90625632

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 17$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $G$ 是连通的，且不存在自环或重边。

样例解释 1

• 只有当不删除边 $1$ 和边 $2$ 时，条件才成立。
• 例如，对顶点 $2$ 进行操作，可以将所有边变为蓝色。
• 其他情况下，图会变为非连通，因此不满足条件。

样例解释 3

• 别忘了对 $998244353$ 取模。

由 ChatGPT 4.1 翻译