8350: BZOJ4350:括号序列再战猪猪侠

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

括号序列与猪猪侠又大战了起来。 众所周知,括号序列是一个只有(和)组成的序列,我们称一个括号 序列S合法,当且仅当: 1.( )是一个合法的括号序列。 2.若A是合法的括号序列,则(A)是合法的括号序列。 3.若A,B是合法的括号序列,则AB是合法的括号序列。 我们考虑match[i]表示从左往右数第i个左括号所对应的是第几个右 括号,现在他得到了一个长度为2n的括号序列,给了你m个信息,第i 个信息形如ai,bi,表示match[ai]<match[bi],要你还原这个序列。 但是你发现这个猪猪侠告诉你的信息,可能有多个括号序列合法;甚 至有可能告诉你一个不存在合法括号序列的信息! 你最近学了取模运算,你想知道答案对998244353(7*17*2^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


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: