Problem Description

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

Input Format

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 Format

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

4 5
1 2
1 3
2 3
2 4
3 4

8

Hint

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