题目描述

$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$ 人組がペアとして異なることをいいます。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

操作方法としてあり得るものの数を $998244353$ で割った余りを出力せよ。

题目大意

题目描述

一共 $2N$ 个学生站成一排，其中有 $M$ 对朋友关系。老师每次从队列中挑出两个相邻的学生作为同桌。为了关系和睦，每次选出的两个学生必须是朋友关系。选出的两个学生离开队列，空出来的位置左右合拢。

请问老师有多少种方式选完所有学生？对于两种选人的方案，即使同桌关系相同，只要离开队列的顺序不同，也算是不同的方案。

输入格式

先输入一行两个整数 $N$、$M$，然后输入 $M$ 行数据，每行两个数 $A_i$ 和 $B_i$，表示两个同学的朋友关系。

输出格式

一个数，为所得方案数对 $998244353$ 取模后得到的值。

2 3
1 2
1 4
2 3

1

2 2
1 2
3 4

2

2 2
1 3
2 4

0

提示

制約

• $1\ \leq\ N\ \leq\ 200$
• $0\ \leq\ M\ \leq\ N(2N-1)$
• $1\ \leq\ A_i\ <\ B_i\ \leq\ 2N$
• $(A_i,\ B_i)$ はすべて異なる。
• 入力は全て整数である。

Sample Explanation 1

$1$ 度目の操作で生徒 $2$ と生徒 $3$ を選び、 $2$ 度目の操作で生徒 $1$ と生徒 $4$ を選ぶのが 唯一の操作方法です。 $1$ 度目の操作で生徒 $1$ と生徒 $2$ を選ぶと、 生徒 $3$ と生徒 $4$ が残りますが、この $2$ 人は仲が悪いため $2$ 度目の操作でペアにすることができません。 よって、 $1$ を出力します。

Sample Explanation 2

$1$ 度目の操作で生徒 $1$ と生徒 $2$ を選び、 $2$ 度目の操作で生徒 $3$ と生徒 $4$ を選ぶのが $1$ 通り、 $1$ 度目の操作で生徒 $3$ と生徒 $4$ を選び、 $2$ 度目の操作で生徒 $1$ と生徒 $2$ を選ぶのが $1$ 通りであわせて $2$ 通りあります。 この $2$ つが区別されることに注意してください。

Sample Explanation 3

$1$ 度目の操作で選べるペアが無いため条件をみたす操作方法は無く、 $0$ を出力します。