题目描述

给定一张包含 $n$ 个点 $m$ 条边的简单无向连通图，点的编号为 $1\sim n$。

你需要求出有多少集合对 $S,T\sube \{1,2,\dots,n\}$，满足对于任意的 $i\in S$，要么 $i$ 也 $\in T$，要么存在 $x,y\in T$（$x\neq y$），满足存在一条从 $x$ 到 $y$ 的简单路径经过 $i$。

注意，集合对 $S,T$ 可以为空集。

输出答案对 $998244353$ 取模后的结果。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$，描述图上的一条边。保证图连通，无自环、重边。

输出格式

共一行一个整数，表示满足题目条件的集合对 $S,T$ 的数量对 $998244353$ 取模后的结果。

样例

2 1
1 2

9

样例解释 1

所有合法的集合 $S,T$ 为：

1. $S=\{\},T=\{\}$。
2. $S=\{\},T=\{1\}$。
3. $S=\{\},T=\{2\}$。
4. $S=\{\},T=\{1,2\}$。
5. $S=\{1\},T=\{1\}$。
6. $S=\{1\},T=\{1,2\}$。
7. $S=\{2\},T=\{2\}$。
8. $S=\{2\},T=\{1,2\}$。
9. $S=\{1,2\},T=\{1,2\}$。

9 10
8 3
6 8
8 5
1 6
6 2
4 6
8 2
1 7
9 6
5 3

80995

20 36
4 7
2 13
18 11
6 14
4 20
5 4
1 9
19 4
6 8
11 15
4 11
4 18
16 9
16 4
18 15
3 18
4 6
5 7
20 6
20 8
8 14
19 13
12 9
4 8
4 15
20 14
3 10
12 1
17 16
13 4
4 14
10 18
4 2
16 12
19 2
1 16

211240350

数据范围

本题使用子任务捆绑测试。

对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$n-1\le m\le 10^6$，$1\le u_i,v_i\le n$。保证图连通，无自环、重边。