题目背景

题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

题目描述

括号序列是一个仅由 () 构成的序列。以下的括号序列是合法的：

1. () 是一个合法序列。
2. 如果 A 是一个合法序列，则 (A) 也是一个合法序列。
3. 如果 A 和 B 都是合法序列，则 AB 也是一个合法序列。

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

现在得到了一个长度为 $2n$ 的括号序列，提供 $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

提示

对于所有数据，保证 $1\leq T\leq 5$，$1\leq n\leq 300$，$1\leq a_i,b_i\leq n$。