AT_iroha2019_day4_g 真実の魔法陣

[problemUrl]: https://atcoder.jp/contests/iroha2019-day4/tasks/iroha2019_day4_g

一行目に、魔法陣のサイズ$ N $ と、既に組まれているペアの個数 $ K $ が与えられます。 続く$ K $ 行に、既に組まれているペアが与えられます。 > $ N $ $ K $ $ a_1 $ $ b_1 $ $ : $ $ 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,..,a_K,b_1,b_2,..,b_K $はすべて異なる ### 解説 [解説](https://img.atcoder.jp/iroha2019-day4/editorial-G.pdf) ### Sample Explanation 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)