← 返回题目列表

AtCoder · abc217_f

I. 配对

中文机器翻译题面 查看原题

分数: 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.