题目描述

括号序列是一个只有 ( 和 ) 组成的序列，我们称一个括号序列 $S$ 合法，当且仅当:

• () 是一个合法的括号序列。
• 若 $A$ 是合法的括号序列，则 ($A$) 是合法的括号序列。
• 若 $A$ 和 $B$ 是合法的括号序列，则 $AB$ 是合法的括号序列。

定义 $match_i$ 表示从左往右数第 $i$ 个左括号所对应的是第几个右括号。

现有一个一个长度为 $2\times n$ 的括号序列，你得到了 $m$ 条信息，第 $i$ 个信息形如 $a_i,b_i$，表示 $match_{a_i}<match_{b_i}$。

请输出满足条件的括号序列的数量对 $998244353$ 取模后的结果。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行两个整数 $n,m$，$n$ 表示有几个左括号，$m$ 表示信息数。

接下来 $m$ 行，每行两个数 $a_i,b_i$。

输出格式

对于每组数据，输出一个数表示答案。

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

提示

对于 $100\%$ 的数据，满足 $1\le n,m\le 300$，$1\le T\le 5$，$1\le a_i,b_i\le n$。

题目来源

没有写明来源