我们设 \(dp_{i,j}\) 表示第 \(i\) 到第 \(j\) 个括号合并为序列且最外层不是括号 \(i\) 的可能性，\(f_{i,j}\) 表示最外层是括号 \(i\) 的可能性。则有：
\[\begin{cases} dp_{i,j}=\sum f_{i,k}(dp_{k+1,j}+f_{k+1,j})\\ f_{i,j}=dp_{i+1,j}+f_{i+1,j} \end{cases} \]当然，并不是所有情况都能合并，所以需要维护 \(p_{i,j,k}\) 和 \(q_{i,j,k}\)，表示 \(k\) 能否接在 \(i\) 到 \(j\) 的左侧/包住 \(i\) 到 \(j\)。
时间、空间复杂度均为 \(O(n^3)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=305,md=998244353;
int t,n,m,f[N][N],dp[N][N];
int p[N][N][N],q[N][N][N];
void solve(){
memset(dp,0,sizeof(dp));
memset(f,0,sizeof(f));
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
cin>>n>>m;
int flag=0;
while(m--){
int x,y;cin>>x>>y;
if(x==y||flag){
flag=1;
continue;
}if(x<y) q[y][y][x]=1;
else p[x][x][y]=1;
}if(flag){
cout<<"0\n";
return;
}for(int i=1;i<=n;i++)
f[i][i]=1;
for(int ln=2;ln<=n;ln++)
for(int i=1,j=ln;j<=n;i++,j++)
for(int k=1;k<=n;k++){
p[i][j][k]|=p[i+1][j][k]|p[i][i][k];
q[i][j][k]|=q[i+1][j][k]|q[i][i][k];
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=1;k<=n;k++)
p[i][j][k]+=p[i][j][k-1];
for(int ln=2;ln<=n;ln++)
for(int i=1,j=ln;j<=n;i++,j++){
for(int k=i;k<j;k++){
if(p[k+1][j][k]-p[k+1][j][i-1]) continue;
if(p[i][k][j]-p[i][k][k]) continue;
dp[i][j]=(dp[i][j]+(ll)f[i][k]*(dp[k+1][j]+f[k+1][j])%md)%md;
}if(!q[i+1][j][i]) f[i][j]=(f[i+1][j]+dp[i+1][j])%md;
}
cout<<(dp[1][n]+f[1][n])%md<<"\n";
}int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--) solve();
return 0;
}