Problem Description

Given a simple undirected connected graph with $n$ vertices and $m$ edges, where the vertices are numbered from $1$ to $n$.

You need to find the number of pairs of sets $S, T \subseteq \{1, 2, \dots, n\}$ such that for any $i \in S$, either $i \in T$ or there exist $x, y \in T$ ($x \neq y$) such that there is a simple path from $x$ to $y$ passing through $i$.

Note that the pairs of sets $S, T$ can be empty sets.

Output the result modulo $998244353$.

Input Format

The first line contains two positive integers $n$ and $m$.

The next $m$ lines each contain two positive integers $u_i$ and $v_i$, describing an edge in the graph. The graph is guaranteed to be connected, with no self-loops or multiple edges.

Output Format

Output a single integer, which is the number of pairs of sets $S, T$ that satisfy the conditions, modulo $998244353$.

Sample Input and Output

Sample Input #1

2 1
1 2

Sample Output #1

9

Sample Input #2

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

Sample Output #2

80995

Sample Input #3

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

Sample Output #3

211240350

Notes/Hints

[Sample Explanation 1]

All valid pairs of sets $S, T$ are:

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\}$

[Data Range]

This problem uses subtask-based testing.

For $100\%$ of the data, $2 \le n \le 5 \times 10^5$, $n-1 \le m \le 10^6$, $1 \le u_i, v_i \le n$. The graph is guaranteed to be connected, with no self-loops or multiple edges.

见题面 Input 部分

见题面 Output 部分