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题目来源
没有写明来源