P6790 [SNOI2020] Spanning Tree.

Given an undirected connected graph $G$. It is known that after deleting one edge, $G$ becomes a cactus (cactus: an undirected connected graph in which no two simple cycles share a common edge). Find the number of spanning trees of $G$. Output the result modulo $998244353$.

The first line contains two integers $n, m$, denoting the number of vertices and edges of graph $G$. The next $m$ lines each contain two positive integers $u, v$ separated by a space $(1 \le u, v \le n)$, denoting an edge $(u, v) \in G$.

Output one line with one integer, denoting the number of spanning trees of $G$ modulo $998244353$.

Constraints: For all testdata, $1 \le n \le m \le 2 \times 10^5$. - For $10\%$ of the testdata, $1 \le n = m \le 2000$. - For another $40\%$ of the testdata, $1 \le n, m \le 10^5$ and $G$ itself is a cactus. - For the remaining $50\%$ of the testdata, there are no special constraints. Translated by ChatGPT 5