Background

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or the problem setter who authorized BZOJ to use it. If you are the copyright owner and believe that we have infringed your rights, please contact us.

Problem Description

A bracket sequence is a sequence consisting only of () . The following bracket sequences are valid:

1. () is a valid sequence.
2. If A is a valid sequence, then (A) is also a valid sequence.
3. If both A and B are valid sequences, then AB is also a valid sequence.

Define $match_i$ as follows: counting from left to right, for the $i$-th left parenthesis, $match_i$ is the index (among right parentheses, from left to right) of the right parenthesis that matches it.

Now you are given a bracket sequence of length $2n$. You are also given $m$ pieces of information. The $i$-th piece is of the form $a_i, b_i$, meaning $match_{a_i} < match_{b_i}$.

Ask: based on this information, how many ways are there to restore a valid bracket sequence? Output the answer modulo $998244353$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains two positive integers $n, m$. Here $n$ is the number of left parentheses, and $m$ is the number of constraints.

The next $m$ lines each contain two positive integers $a_i, b_i$.

Output Format

For each test case, output one integer representing the answer.

5
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1

1
42
1
2
0

Hint

For all test cases, it is guaranteed that $1 \leq T \leq 5$, $1 \leq n \leq 300$, and $1 \leq a_i, b_i \leq n$.

Translated by ChatGPT 5