/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2N 人の生徒が一列に並んでおり、左から順に生徒 1 , 生徒 2 , \ldots , 生徒 2N と番号が付いています。 2N 人の生徒はどの 2 人も互いに仲が良いか悪いかのどちらかであり、 具体的には 1\leq i\leq M について生徒 A_i と生徒 B_i の仲が良く、これら以外のどの 2 人も仲が悪いです。
先生は以下の操作を N 回繰り返して、 2 人組のペアを N 組作ることにしました。
- 隣り合う 2 人であって仲が良いような 2 人をペアとして選び、列から抜く。
- 抜けた 2 人が列の端でなかったならば、その後、列を詰める。すなわち、抜けた 2 人の左右にいた 2 人が新しく隣り合う。
このとき、 N 回の操作方法としてあり得るものの数を 998244353 で割った余りを求めてください。 ただし N 回の操作方法が異なるとは、ある 1\leq i\leq N が存在して、 i 回目の操作で 選ばれた 2 人組がペアとして異なることをいいます。
制約
- 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
1 度目の操作で生徒 2 と生徒 3 を選び、
2 度目の操作で生徒 1 と生徒 4 を選ぶのが
唯一の操作方法です。
1 度目の操作で生徒 1 と生徒 2 を選ぶと、
生徒 3 と生徒 4 が残りますが、この 2 人は仲が悪いため 2 度目の操作でペアにすることができません。
よって、 1 を出力します。
入力例 2
2 2 1 2 3 4
出力例 2
2
1 度目の操作で生徒 1 と生徒 2 を選び、 2 度目の操作で生徒 3 と生徒 4 を選ぶのが 1 通り、 1 度目の操作で生徒 3 と生徒 4 を選び、 2 度目の操作で生徒 1 と生徒 2 を選ぶのが 1 通りであわせて 2 通りあります。 この 2 つが区別されることに注意してください。
入力例 3
2 2 1 3 2 4
出力例 3
0
1 度目の操作で選べるペアが無いため条件をみたす操作方法は無く、 0 を出力します。
Score : 500 points
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.