Spanning Tree Count in an Almost Cactus Graph

Given an undirected connected graph \(G\) with the following property: there exists an edge whose removal turns \(G\) into a cactus graph (i.e. an undirected connected graph in which no two simple cycles share a common edge). Your task is to compute the number of spanning trees of \(G\) modulo \(998244353\).

Definition: A cactus graph is a connected graph in which every edge belongs to at most one simple cycle.

Hint: One effective method to count spanning trees is by using Kirchhoff's Matrix Tree Theorem. Construct the Laplacian matrix \(L\) for \(G\) where \(L[i][i]\) equals the degree of vertex \(i\) and \(L[i][j] = -1\) if there is an edge between \(i\) and \(j\) (and \(0\) otherwise). Remove any one row and the corresponding column from \(L\); then the determinant of the resulting matrix, taken modulo \(998244353\), is the number of spanning trees.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(n\) is the number of vertices and \(m\) is the number of edges). Each of the following \(m\) lines contains two integers \(u\) and \(v\) (1-based indices) denoting an undirected edge between vertices \(u\) and \(v\).

outputFormat

Output a single integer — the number of spanning trees of \(G\) modulo \(998244353\).

sample

3 3
1 2
2 3
3 1

3