#4350. 括号序列再战猪猪侠

题目描述

括号序列与猪猪侠又大战了起来。

众所周知，括号序列是一个只有(和)组成的序列，我们称一个括号

序列S合法，当且仅当:

1.( )是一个合法的括号序列。

2.若A是合法的括号序列，则(A)是合法的括号序列。

3.若A，B是合法的括号序列，则AB是合法的括号序列。

我们考虑match[i]表示从左往右数第i个左括号所对应的是第几个右

括号，现在他得到了一个长度为2n的括号序列，给了你m个信息，第i

个信息形如ai,bi，表示match[ai]<match[bi]，要你还原这个序列。

但是你发现这个猪猪侠告诉你的信息，可能有多个括号序列合法；甚

至有可能告诉你一个不存在合法括号序列的信息！

你最近学了取模运算，你想知道答案对998244353(7172^23+1)取

模的结果，这个模数是一个质数。

输入格式

第一行一个正整数T,T< = 5，表示数据组数。

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

接下来m行，每行两个数ai,bi，1< = ai,bi< = n。

输出格式

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

样例

样例输入

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% 的数据，保证 n < = 300