Make Pair

题目描述

有 $2N$ 名学生排成一排，从左到右编号为 $1$, $2$, $\ldots$, $2N$。 对于任意一对学生，他们要么关系良好，要么关系不和。 具体地，对于每个 $1\leq i\leq M$，学生 $A_i$ 和学生 $B_i$ 关系良好；对于其余的学生对，他们关系不和。 老师将进行如下操作 $N$ 次以组成 $N$ 对学生。

选择一对相邻且关系良好的学生，将他们配对，并将他们从队列中移除。 如果被移除的学生不在队列的两端，则收拢空隙，使得被移除学生左侧和右侧的两个学生现在相邻。

求完成该操作 $N$ 次的方案数，对 $998244353$ 取模。 当存在 $1\leq i\leq N$ 使得在第 $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 2
1 2
3 4

2

2 2
1 3
2 4

0

提示

$1 \leq N \leq 200$ $0 \leq M \leq N(2N-1)$ 1 \leq A_i < B_i \leq 2N 所有对 $(A_i, B_i)$ 互不相同。 输入中的所有数值均为整数。唯一能完成该过程的方式是先选择学生 $2$ 和 $3$，再选择学生 $1$ 和 $4$。 如果第一步选择了学生 $1$ 和 $2$，则学生 $3$ 和 $4$ 会剩下，它们关系不和，因此无法在第二步配对。
因此，应当输出 $1$.
有两种完成该过程的方式：一种是第一步选择学生 $1$ 和 $2$，第二步选择学生 $3$ 和 $4$；另一种是第一步选择学生 $3$ 和 $4$，第二步选择学生 $1$ 和 $2$。 注意这两种方式是不同的。
由于第一步无法选择任何一对，因此不存在完成该过程的方式，应当输出 $0$.

标签: AtCoder|abc217F

来源

AtCoder|abc217F