我们知道，一个长度为 \(n\) 的合法括号序列的种数就是第 \(\frac n 2\) 个卡特兰数（当然 \(n\) 是奇数答案肯定就是 \(0\)）
我们可以发现一件事情，如果两个区间相互包含，那么就可以将大区间分为中间被包含的小区间的部分和外面没有被小区间覆盖的部分。
如果两个区间相交，那么就可以分为三个部分，左半部分、中间相交部分、右半部分。
以上的所有 部分 都要满足是一个合法的括号序列才能满足条件。
但是很显然，题目给出的数据肯定会有一堆相交和包含的关系，我们需要将其理清。
我们可以发现两个位置在同一个 部分 当且仅当覆盖其上的区间完全相同，那么我们可以对每个区间一个特征值，然后使用 Xor-Hash 做到将所有关系理清，然后用 \(Map/Set\) 存储每一个 Hash 值的数量，最后将所有的卡特兰数相乘即可。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 6e5 + 8, MOD = 998244353;
int n,k;
int t;
ll a[NN];
ll fac[NN],inv[NN],cat[NN];
map<ll,ll> vis;
ll ksm(ll x,ll k){
ll res = 1;
while(k){
if(k & 1) res = res * x % MOD;
x = x * x % MOD;
k >>= 1;
}
return res;
}
ll binom(int n,int m){
if(n < m) return 0;
return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}
int main(){
mt19937 rnd(time(0));
scanf("%d",&t);
fac[0] = inv[0] = 1;
for(int i = 1; i <= NN - 2; ++i) fac[i] = fac[i-1] * i % MOD;
inv[NN - 2] = ksm(fac[NN - 2], MOD - 2);
for(int i = NN - 2; i >= 1; --i) inv[i-1] = inv[i] * i % MOD;
for(int i = 0; i <= NN - 2; ++i) cat[i] = binom(2 * i,i) * ksm(i + 1,MOD - 2) % MOD;
while(t--){
vis.clear();
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; i++) a[i] = 0;
for(ll i = 1,l, r; i <= k; i++) {
scanf("%lld%lld",&l,&r);
ll t = 1ll * rnd() * rnd() ^ rnd();
a[l] ^= t, a[r + 1] ^= t;
}
ll t = 1ll * rnd() * rnd() ^ rnd();
a[1] ^= t, a[n + 1] ^= t;
for(int i = 1; i <= n; i++) a[i] = a[i] ^ a[i - 1], ++vis[a[i]];
ll ans = 1;
for(auto i : vis) {
int cnt = i.second;
if (cnt % 2 == 1) ans = 0;
else ans = ans * cat[cnt / 2] % MOD;
}
printf("%lld\n",ans);
}
}