Description

If, in an undirected connected graph with no self-loops and no multiple edges, every edge belongs to at most one simple cycle, we call it a cactus. A simple cycle is a cycle that does not pass through any vertex more than once.

Now Jiutiao Kelian has an undirected connected graph with no self-loops and no multiple edges, but she thinks the graph has too few edges, so she wants to add some new edges to it. Meanwhile, to store this undirected graph conveniently, the number of edges should not be too large. After weighing these factors, she wants the graph obtained after adding edges to be a cactus.

It is not hard to see that there are many valid ways to add edges. She wants to know how many different ways there are in total.

Two ways of adding edges are different if and only if there exists an edge that is in one way but not in the other.

Input Format

Multiple test cases. The first line contains an integer $T$ denoting the number of test cases.

For each test case, the first line contains two integers $n, m$, denoting the number of vertices and the number of edges.

Then $m$ lines follow. Each line contains two integers $u, v$ ($1 \le u, v \le n, u \ne v$) describing an edge. It is guaranteed that the input graph is connected and has no self-loops or multiple edges.

Output Format

For each test case, output one integer denoting the number of valid ways. Since the answer may be large, output it modulo $998244353$.

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

2
8

Hint

Sample explanation.

For the first sample, the valid ways are $\{\}, \{(2,3)\}$, for a total of $2$.

Constraints

Translated by ChatGPT 5