区間DPとなる． ペアを作って取り除いていく場合の数を数えるが， これは取り除く順序を木構造にして，それを数え上げる問題． 今回は，木の形が決まっていない．
\([l,r)\) に対する答えを，より小さい区間に帰着させたい． \(i \in [l,r),\ i += 2\) に対して，\([l,i), [i,r)\) の区間に分割する．
- \([l,i)\) における取り除き方は \(dp_{l,i}\) 通り，
- \([i,r)\) における取り除き方は \(dp_{i,r}\) 通り，
- \([l,i)\) における \(x := \frac{i-l}{2}\)組と \([i,r)\) における \(y := \frac{r-i}{2}\)組の 消す順序は \({}_{x+y}C_{x}\) 通り． \(x\)個の \(l\) と \(y\) 個の \(r\) を並べた順列が，消す順序と対応する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
n *= 2;
vvll good(n, vll(n));
rep(i,m){
ll a,b; cin >> a >> b;
--a,--b;
good[a][b] = true;
good[b][a] = true;
}
Comb<mint, 1000> co;
rep(i,n) dp[i][i] = 1;
for(ll w = 2; w <= n; w += 2){ // rem : w <= n
rep(l,n){
ll r = l + w;
if(r > n) break;
if(good[l][r-1]){
dp[l][r] += dp[l+1][r-1];
}
for(ll i = l+2; i < r; i += 2) {
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
p[a][b] = true;
p[b][a] = true;
}
// [l,r)
// dp[l][r]
Comb<mint, 1000> co;
rep(i,n) dp[i][i] = 1;
for(ll w = 2; w <= n; w += 2){ // rem : w <= n
rep(l,n){
ll r = l + w;
if(r > n) break;
for(ll i = l; i < r; i += 2) if(p[i][r-1]){
dp[l][r] += dp[l][i] * dp[i+1][r-1] * co.nCr((r-l)/2, (i-l)/2);
}
}
}
cout << dp[0][n].val() << endl;
return 0;
}
*1:i-l)%2 == 0);
assert((r-i)%2 == 0);
ll x = (i-l)/2;
ll y = (r-i)/2;
dp[l][r] += dp[l][i] * dp[i][r] * co.nCr(x+y,x);
}
}
}
cout << dp[0][n].val() << endl;
return 0;
}
