A connected, undirected graph with no self-loops or multiple edges is called a cactus if every edge belongs to at most one simple cycle. A simple cycle is a cycle that does not pass through any vertex more than once.
Cactus (check), Not a cactus (edges shared by two cycles) (cross), Not a cactus (not a connected graph) (cross)
Keli has a connected, undirected graph with no self-loops or multiple edges. She feels that the number of edges in this graph is too small, so she wants to add some new edges to it. At the same time, to keep the graph easy to store, she does not want too many edges. After careful consideration, she wants the resulting graph to be a cactus.
It is not hard to see that there are many valid ways to add edges. Keli wants to know the total number of different ways to add edges. Two ways to add edges are considered different if and only if there exists an edge in one way that is not present in the other.
Input
The input consists of multiple test cases. The first line contains an integer $T$, representing the number of test cases.
For each test case, the first line contains two integers $n$ and $m$, representing the number of vertices and edges in the graph, respectively.
The next $m$ lines each contain two integers $u, v$ ($1 \le u, v \le n, u \neq v$), representing an edge in the graph. It is guaranteed that the input graph is connected and contains no self-loops or multiple edges.
Output
For each test case, output an integer representing the number of ways to add edges. Since the number of ways can be very large, please output the result modulo $998244353$.
Examples
Input 1
2 3 2 1 2 2 3 5 4 1 2 2 3 2 4 1 5
Output 1
2 8
Note
For the first sample case, the valid ways to add edges are $\emptyset$ and $\{(2, 3)\}$, for a total of $2$ ways.
Constraints
| Test Case ID | $\sum n$ | $m$ | Other Constraints |
|---|---|---|---|
| 1 | $\le 5$ | $\le 10$ | None |
| 2 | $\le 2000$ | $\le 2 \times 10^5$ | None |
| 3 | |||
| 4 | $\le 10^5$ | $= n - 1$ | Graph is a chain |
| 5 | |||
| 6 | |||
| 7 | |||
| 8 | $\le 5 \times 10^5$ | $\le 10^6$ | None |
| 9 | |||
| 10 |
For 100% of the data, it is guaranteed that $1 \le m \le \frac{n(n-1)}{2}$ and $\sum m \le 10^6$.
Note: $T$ may be large, please be careful with the complexity of initialization.
In the large data files provided to the contestants, four sets of data satisfy the conditions for test cases 2, 4, 6, and 8, respectively.