配对

题目描述

有 $2N$ 个学生排成一排，从左到右编号为 $1,2,\ldots,2N$。 任意两个学生之间的关系要么是友好，要么是不友好。 具体来说，对于每个 $1\le i\le M$，学生 $A_i$ 和学生 $B_i$ 友好；其余两个学生之间的关系不友好。

老师要进行 $N$ 次以下操作，组成 $N$ 对学生。

选择两个相邻且友好的学生，把他们配对，然后从队伍中移除。

如果被移除的学生不在队伍两端，就合拢空位，使原来在他们左右两侧的两个学生变为相邻。

求完成 $N$ 次操作的方法数，对 $998244353$ 取模。 当存在 $1\le i\le N$，使得两种操作方式在第 $i$ 次操作中选择的学生对不同时，认为这两种操作方式不同。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出完成整个操作过程的方法数，对 $998244353$ 取模。

样例

2 3
1 2
1 4
2 3

1

完成操作过程的唯一方式是第一次选择学生 $2$ 和 $3$，第二次选择学生 $1$ 和 $4$。 如果第一次选择学生 $1$ 和 $2$，则剩下学生 $3$ 和 $4$，他们不友好，无法在第二次操作中配对。

因此应输出 $1$。

2 2
1 2
3 4

2

完成操作过程有两种方式：一种是第一次选择学生 $1$ 和 $2$、第二次选择学生 $3$ 和 $4$；另一种是第一次选择学生 $3$ 和 $4$、第二次选择学生 $1$ 和 $2$。 注意这两种方式被认为是不同的。

2 2
1 3
2 4

0

由于第一次操作无法选择任何一对学生，所以不存在完成操作过程的方式，应输出 $0$。

数据范围

• $1 \le N \le 200$
• $0 \le M \le N(2N-1)$
• $1 \le A_i \lt B_i \le 2N$
• 所有 $(A_i,B_i)$ 两两不同。
• 输入中的所有值均为整数。