F - 成对

得分: $500$ 分

问题描述

一共有 $2N$ 名学生从左到右排成一行，编号为 $1$, $2$, $\ldots$, $2N$。 对于所有两名学生的配对，他们之间要么关系好，要么关系不好。 具体来说，对于每个 $1\leq i\leq M$，学生 $A_i$ 和学生 $B_i$ 的关系是好的；对于其他所有的两名学生，他们的关系是不好的。

老师准备对这些学生进行以下操作 $N$ 次，每次操作会形成一对学生。

• 选择两个关系好的相邻学生，将他们配对，并从排列中删除他们。
• 如果被删除的学生不在排列的首尾位置上，则将首尾相连，使得被删除的学生左右的两名学生成为相邻的学生。

求在进行 $N$ 次操作的过程中，完成这些操作的可能方案数，对 $998244353$ 取模。

两种进行 $N$ 次操作的方式被认为是不同的，当且仅当存在一个 $1\leq i\leq N$，使得这两种方式在第 $i$ 次操作中选择的学生对不同。

限制

• $1 \leq N \leq 200$
• $0 \leq M \leq N(2N-1)$
• $1 \leq A_i < B_i \leq 2N$
• 所有的配对 $(A_i, B_i)$ 互不相同。
• 所有输入数据都是整数。

输入

从标准输入读入数据，数据格式如下：

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_M$ $B_M$

输出

输出完成该过程的可能方案数，对 $998244353$ 取模。

2 3
1 2
1 4
2 3

1

完成该过程的唯一方式是第一次选择学生 $2$ 和学生 $3$，第二次选择学生 $1$ 和学生 $4$。 如果在第一次操作中选择学生 $1$ 和学生 $2$，那么剩下的是学生 $3$ 和学生 $4$，他们之间的关系不好，因此无法在第二次操作中配对。
因此，你应该输出 $1$。

2 2
1 2
3 4

2

完成该过程的两种方式：一种是在第一次操作中选择学生 $1$ 和学生 $2$，在第二次操作中选择学生 $3$ 和学生 $4$；另一种是在第一次操作中选择学生 $3$ 和学生 $4$，在第二次操作中选择学生 $1$ 和学生 $2$。 请注意这两种方式是不同的。

2 2
1 3
2 4

0

由于第一次操作中无法选择一对学生，无法完成该过程，因此你应该输出 $0$。