问题描述

有$2N$个学生，编号为 $1,2,…,2n$。

学生的关系有好有坏，给定$M$对友好学生$(A_i,B_i)$。其余的均为坏学生。

接下来有$N$次操作。

• 把两个相邻的且关系友好的学生剔除。

• 剔除后若留下间隙，两边的学生保持原次序合并。

请问操作$N$次的方案数是多少。

方案数对998244353取模。

约定

• $1\leq N \leq 200$

• $0 \leq M \leq N(2N-1)$

• $1\leq A_i< B_i\leq 2N$

• 给定的$M$对学生都是不相同的。

• 所有输入的数值均为整数。

输入

输入来自以下格式的标准输入：

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$⋮$

$A_M$ $B_M$

输出

请你输出方案数，对998244353取模。

样例输入1

2 3

1 2

1 4

2 3

样例输出1

1

先剔除学生2，3。然后剔除学生1，4。不能先剔除1，2。

样例输入2

2 2

1 2

3 4

样例输出2

2

先剔除学生1，2再剔除学生3，4。先剔除学生3，4，再剔除学生1，2。

样例输入3

2 2

1 3

2 4

样例输出3

0