Problem Description

Given an undirected connected graph $G$ with $n$ vertices and $m$ edges, the vertices are numbered $1,2,\ldots,n$ in order. $G$ has the following special properties:

• Each edge in $G$ belongs to at most one simple cycle.
• $G$ has no multiple edges or self-loops.

A simple cycle means a cycle in which all vertices are distinct, and no edge is repeated.

Please find the number of different spanning trees of $G$. Two spanning trees are different if and only if there exists an edge that appears in one spanning tree but not in the other.

Since the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line contains two positive integers $n,m$, representing the number of vertices and the number of edges of $G$, respectively.

In the next $m$ lines, each line contains two integers $u_i,v_i$, representing an undirected edge connecting vertices $u_i,v_i$.

Output Format

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

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

12

5 4
1 2
1 3
2 4
2 5

1

Hint

For $40\%$ of the testdata, it is guaranteed that $1\le n\le 8$ and $1\le m\le 10$.

For $60\%$ of the testdata, it is guaranteed that $1\le n\le 2000$ and $1\le m\le 2000$.

For all testdata, it is guaranteed that $1\le n\le 10^5$, $1\le m\le 10^5$, and $1\le u_i,v_i\le n$.

Translated by ChatGPT 5