分数: 500 点
问题陈述
有 2N 学生站成一排,编号 1, 2, \ldots, 2N 从左到右。 对于所有的两名学生来说,他们的关系要么好,要么不好。 具体来说,对于每个 1\leq i\leq M,学生 A_i 和学生 B_i 关系良好;对于剩下的两名学生来说,他们的关系并不好。
老师要做如下操作 N 次形成 N 两个学生对。
- 选择两个关系良好的相邻学生,将他们配对,然后将他们从行中删除。
- 如果被移除的学生不在行的末尾,请缩小间隙,以便被移除的学生左侧和右侧的两个学生现在相邻。
求模数 998244353,执行该操作的可能方法 N 次。 两种操作方式 N 存在时被认为不同 1\leq i\leq N 这样,在 i-th 操作在这两种方式上是不同的。
约束
- 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.
示例输入 1
2 3 1 2 1 4 2 3
示例输出 1
1
完成该程序的唯一方法是选择学生 2 和 3 中第一和同学 1 和 4 在第二个。
如果学生
第一次操作时选择 1 和 2 ,学生 3 和 4 将保留,他们关系不好,因此无法在第二次操作中配对。
因此,您应该打印 1.
示例输入 2
2 2 1 2 3 4
示例输出 2
2
有两种方法可以完成该程序:一种方法是选择学生 1 和 2 在第一次操作和学生 3 和 4 在第二个,另一种方式是选择学生 3 和 4 在第一次操作和学生 1 和 2 在第二个。 注意这两种方式是有区别的。
示例输入 3
2 2 1 3 2 4
示例输出 3
0
由于在第一次操作中无法选择任何对,因此无法完成该过程,因此您应该打印 0.