Repovive

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$ .

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Triangle with edges $(1,2)$ , $(2,3)$ , $(1,3)$ .

For DFS order $1,2,3$ : vertex $2$ must connect to $1$ (so edge $(1,2)$ is required), and vertex $3$ must connect to $1$ or $2$ (so at least one of $(1,3)$ or $(2,3)$ must remain).

Valid subsets: $\{ (1,2),(2,3) \}$ , $\{ (1,2),(1,3) \}$ , $\{$ all three $\}$ .

Answer: 3.

Edges $(1,3)$ , $(2,3)$ only.

Vertex $2$ has no edge to vertex $1$ , so there is no way to achieve DFS order $1,2,3$ .

Answer: 0.

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

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$ .

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Triangle with edges $(1,2)$ , $(2,3)$ , $(1,3)$ .

For DFS order $1,2,3$ : vertex $2$ must connect to $1$ (so edge $(1,2)$ is required), and vertex $3$ must connect to $1$ or $2$ (so at least one of $(1,3)$ or $(2,3)$ must remain).

Valid subsets: $\{ (1,2),(2,3) \}$ , $\{ (1,2),(1,3) \}$ , $\{$ all three $\}$ .

Answer: 3.

Edges $(1,3)$ , $(2,3)$ only.

Vertex $2$ has no edge to vertex $1$ , so there is no way to achieve DFS order $1,2,3$ .

Answer: 0.

5D. DFS Order Counting

Constraints

Input

Output

Samples

Constraints