AT_iroha2019_day4_g 真実の魔法陣

给定一个大小为 $N$ 的魔法阵，以及已经配对的 $K$ 对点。请计算在剩余的点中，如何配对可以使得所有线段的最大交点数（即“复杂度”）最小，并输出在最小复杂度下的配对方案数。

第一行输入魔法阵的大小 $N$ 和已配对的对数 $K$。 接下来的 $K$ 行，每行输入一对已经配对的点。 > $N$ $K$ > $a_1$ $b_1$ > $a_2$ $b_2$ > $\vdots$ > $a_K$ $b_K$

请输出答案。

### 限制条件 - 所有输入均为整数。 - $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, \ldots, a_K, b_1, b_2, \ldots, b_K$ 均互不相同。 ### 说明 [题解](https://img.atcoder.jp/iroha2019-day4/editorial-G.pdf) ### 样例解释 1 魔法阵的最小复杂度为 $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 ``` --- ### 说明 [题解](https://img.atcoder.jp/iroha2019-day4/editorial-G.pdf) 由 ChatGPT 4.1 翻译