【MX-S1-T3】电动力学

给定一张包含 $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

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

__【样例解释 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\}$。 __【数据范围】__ __本题使用子任务捆绑测试。__ 对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$n-1\le m\le 10^6$，$1\le u_i,v_i\le n$。保证图连通，无自环、重边。 | 子任务编号 | $n\le $ | $m\le $ | 特殊性质 | 分值 | | ---------- | -------------- | ------------------ | --------------- | ---- | | $1$ | $10$ | $\frac{n(n-1)}{2}$ | 无 | $10$ | | $2$ | $20$ | $\frac{n(n-1)}{2}$ | 无 | $10$ | | $3$ | $5\times 10^5$ | $n-1$ | $u_i=i,v_i=i+1$ | $10$ | | $4$ | $5\times 10^5$ | $n-1$ | 无 | $20$ | | $5$ | $5\times 10^5$ | $n$ | 无 | $20$ | | $6$ | $5\times 10^5$ | $10^6$ | 无 | $30$ |