Score : $500$ points

问题描述

有$2N$名学生站成一排，从左至右依次编号为$1$, $2$, $\ldots$, $2N$。对于任意两个学生，他们要么关系好要么关系差。具体来说，对于每个$1\leq i\leq M$，学生$A_i$和学生$B_i$关系好；其余的任意两个学生的组合则关系差。

老师打算进行以下操作$N$次来组成$N$对关系好的学生。

• 选择一对相邻且关系好的学生，将他们配对并从队伍中移除。
• 若移除的学生不在队伍的两端，则填补空位，使得原来在被移除学生左右两侧的学生变为相邻。

求出执行这个操作$N$次的不同方法数，结果对$998244353$取模。若存在$1\leq i\leq N$，使得两种执行方式在第$i$次操作中所选的学生对不同，则认为这两种执行方式是不同的。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 09:37:25