Background

Original link: https://oier.team/problems/S1C。

Problem Description

Given a simple undirected connected graph with $n$ vertices and $m$ edges, where the vertices are labeled $1 \sim n$.

You need to count how many ordered pairs of sets $S, T \sube \{1,2,\dots,n\}$ satisfy that for every $i \in S$, either $i$ is also $\in T$, or there exist $x, y \in T$ ($x \neq y$) such that there is a simple path from $x$ to $y$ that passes through $i$.

Note that the set pair $S, T$ may be empty.

Output the answer modulo $998244353$。

Input Format

The first line contains two positive integers $n, m$。

The next $m$ lines each contain two positive integers $u_i, 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 one integer in a single line, representing the number of set pairs $S, T$ that satisfy the condition, modulo $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

Hint

Sample Explanation 1

All valid 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\}$。

Constraints

This problem uses bundled subtasks.

For $100\%$ of the testdata, $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.

Translated by ChatGPT 5