← 返回题目列表

AtCoder · iroha2019_day4_g

G. 真理的魔法圈

中文机器翻译题面 查看原题

配点 : 900 点

故事

“这是什么……?”当我们到达那里时,我们看到了类似魔法阵的东西。它有些地方已经褪色、缺失了,所有人都可以明显看出它是不完整的。
如果到现在为止,我可能没有解决这个问题就回家了。但现在……我想知道“真相”。

問題文

一个巨大的圆圈出现在你的面前。你需要使用这个法阵来完成魔法阵。
什么是魔法阵? 2N 点在圆周上等间隔排列, 它被分成N 对并绘制线段。
在圆周上 2N 点等间隔排列,从某一点开始顺时针移动。 它们的编号最大为 1 减去 2N 。
就在我面前 2N 点中,有些点已经配对并通过线段连接,但有些点尚未配对。你需要决定如何将它们配对并完成魔法圈。

当魔圈的复杂度定义为“相交成圆的线段对的数量”时, 您希望最小化所产生的魔法阵的复杂性。
找出可以最小化魔法阵复杂性的配对方式的数量, 除以10^9+7 求余数。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 300
  • 0 \leq K \leq N
  • 1 \leq a_i,b_i\leq 2N (i=1,2,\dots,K)
  • a_1,a_2,..,a_K,b_1,b_2,..,b_K都不同

入力

第一行,魔法阵的大小N 和已形成对的数量 K 。
继续 已组装的对在K 行中给出。

N  K
a_1 b_1
:
a_K b_K

出力

请打印答案。


入力例 1

3 0

出力例 1

5

魔法阵的最小复杂度是0。
如何形成对以使线段不相交5方法有很多。

入力例 2

7 3
1 13
3 11
9 4

出力例 2

4

最小复杂度是2。复杂性 下面是如何组成一对来实现2形成一对来实现这一点的方法如下。4没错。
、(2,10),(5,6),(7,8),(12,14)
、(2,10),(5,8),(6,7),(12,14)
、(2,14),(5,6),(7,8),(10,12)
、(2,14),(5,8),(6,7),(10,12)

入力例 3

30 15
44 36
1 11
53 21
38 52
8 22
26 42
35 2
23 37
30 58
18 17
3 33
51 9
39 14
12 41
4 49

出力例 3

1136

解説

解説