102175: [AtCoder]ABC217 F - Make Pair

Problem Statement

There are $2N$ students standing in a row, numbered $1$, $2$, $\ldots$, $2N$ from left to right. For all pairs of two students, they are on good or bad terms. Specifically, for each $1\leq i\leq M$, Student $A_i$ and Student $B_i$ are on good terms; for the remaining pairs of two students, they are on bad terms.

The teacher is going to do the following operation $N$ times to form $N$ pairs of two students.

• Choose two adjacent students who are on good terms, pair them, and remove them from the row.
• If the removed students were not at an end of the row, close up the gap so that the two students who were to the left and right of the removed students are now adjacent.

Find the number, modulo $998244353$, of possible ways to do the operation $N$ times. Two ways to do the operation $N$ times are considered different when there exists $1\leq i\leq N$ such that the pair of students chosen in the $i$-th operation is different in those two ways.

Constraints

• $1 \leq N \leq 200$
• $0 \leq M \leq N(2N-1)$
• $1 \leq A_i < B_i \leq 2N$
• All pairs $(A_i, B_i)$ are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

Output

Print the number of possible ways to complete the procedure, modulo $998244353$.

Sample Input 1

2 3
1 2
1 4
2 3

Sample Output 1

1

The only way to complete the procedure is to choose Students $2$ and $3$ in the first and Students $1$ and $4$ in the second. If Students $1$ and $2$ are chosen in the first operation, Students $3$ and $4$ will remain, who are on bad terms and thus cannot be paired in the second operation.
Thus, you should print $1$.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

2

There are two ways to complete the procedure: one way is to choose Students $1$ and $2$ in the first operation and Students $3$ and $4$ in the second, and the other way is to choose Students $3$ and $4$ in the first operation and Students $1$ and $2$ in the second. Note that these two ways are distinguished.

Sample Input 3

2 2
1 3
2 4

Sample Output 3

0

Since no pair can be chosen in the first operation, there is no way to complete the procedure, so you should print $0$.

问题描述

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

老师将要做 $N$ 次操作来形成 $N$ 对好朋友。

• 选择一对相邻的好朋友学生，将他们配对，并从队伍中移除。
• 如果移除的学生不在队伍的两端，那么将队伍的空隙关闭，使得原本在移除的学生左边和右边的两个学生现在相邻。

求出可以完成 $N$ 次操作的方法的数量，对 $998244353$ 取模。 如果在 $1\leq i\leq N$ 中存在一个 $i$，使得在第 $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$ 取模。

样例输入 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

完成该操作有两