1D. DFS Order Counting

Consider a connected undirected graph with $n$ vertices labeled $1,2,\ldots,n$ and $m$ edges.

For each vertex, fix an ordering of its adjacency list (i.e., an order in which its neighbors will be considered).
Once these adjacency orders are fixed, running the standard depth-first search (DFS) starting from vertex $1$ becomes fully deterministic: whenever DFS is at a vertex, it scans its neighbors in the prescribed order and recursively visits the first unvisited neighbor it encounters, continuing until all reachable vertices are processed.

The DFS order of the graph (under the chosen adjacency orders) is defined as the sequence of vertices in the order they are first discovered by this DFS.

We call the graph nice if there exists a choice of adjacency-list orderings for all vertices such that the DFS order is exactly $1,2,\ldots,n$.

You are given a connected graph with $n$ vertices and $m$ edges. Count the number of subsets of edges whose removal makes the remaining graph nice.

Output the answer modulo $998244353$.

Constraints

• $1 \le t \le 100$
• $1 \le n \le 5000$
• $n-1 \le m \le 5000$
• $1 \le u, v \le n$, $u \ne v$
• The input graph is connected and has no self-loops or multiple edges.
• The sum of $n$ over all test cases does not exceed $5000$.
• The sum of $m$ over all test cases does not exceed $5000$.