#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/g

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/g

Repovive

Removing Graph via a Matching - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

7G. Removing Graph via a Matching

3500 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

You are given a simple undirected graph with $n$ vertices numbered from $1$ to $n$ . The number $n$ is even.

Initially, no vertex is deleted. In one operation, you may choose an edge $(u,v)$ such that both $u$ and $v$ are not deleted yet, and every vertex $x$ with $\min(u,v) < x < \max(u,v)$ has already been deleted. Then vertices $u$ and $v$ are deleted.

A deletion sequence is valid if it contains exactly $\frac{n}{2}$ operations and all vertices are deleted at the end.

Find the number of valid deletion sequences modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$2 \le n \le 5000$
$0 \le m \le 5000$
$n$ is even
The graph is simple
The sum of $n$ over all test cases is at most $5000$
The sum of $m$ over all test cases is at most $5000$

Input

t

\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

Output

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

Samples

Input

Case 1

2 1
1 2

Case 2

4 2
1 2
3 4

Case 3

4 2
1 4
2 3

Case 4

Case 5

Explanation

Case 1

There is only one edge, so the only possible sequence deletes vertices $1$ and $2$ .

Case 2

Both edges can be used, and they can be chosen in either order.

Case 3

First vertices $2$ and $3$ must be deleted, then vertices $1$ and $4$ can be deleted.

Case 4

There are two sequences using edges $(1,2)$ and $(3,4)$ . There is also one sequence using $(2,3)$ first and $(1,4)$ second.

Case 5

Every valid sequence repeatedly deletes two currently adjacent remaining vertices. For this graph, there are $15$ such sequences.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given a simple undirected graph with $n$ vertices numbered from $1$ to $n$ . The number $n$ is even.

A deletion sequence is valid if it contains exactly $\frac{n}{2}$ operations and all vertices are deleted at the end.

Find the number of valid deletion sequences modulo $998244353$ .

$1 \le t \le 10^4$
$2 \le n \le 5000$
$0 \le m \le 5000$
$n$ is even
The graph is simple
The sum of $n$ over all test cases is at most $5000$
The sum of $m$ over all test cases is at most $5000$

t

\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

There is only one edge, so the only possible sequence deletes vertices $1$ and $2$ .

First vertices $2$ and $3$ must be deleted, then vertices $1$ and $4$ can be deleted.

There are two sequences using edges $(1,2)$ and $(3,4)$ . There is also one sequence using $(2,3)$ first and $(1,4)$ second.

Every valid sequence repeatedly deletes two currently adjacent remaining vertices. For this graph, there are $15$ such sequences.