P10674 [MX-S1-T3] Electrodynamics.

Original link: 。

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$。

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 one integer in a single line, representing the number of set pairs $S, T$ that satisfy the condition, modulo $998244353$。

__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. | Subtask ID | $n\le $ | $m\le $ | Special Property | Score | | ---------- | -------------- | ------------------ | ---------------- | ----- | | $1$ | $10$ | $\frac{n(n-1)}{2}$ | None | $10$ | | $2$ | $20$ | $\frac{n(n-1)}{2}$ | None | $10$ | | $3$ | $5\times 10^5$ | $n-1$ | $u_i=i,v_i=i+1$ | $10$ | | $4$ | $5\times 10^5$ | $n-1$ | None | $20$ | | $5$ | $5\times 10^5$ | $n$ | None | $20$ | | $6$ | $5\times 10^5$ | $10^6$ | None | $30$ | Translated by ChatGPT 5