Problem Description

Input Format

The first line contains the size of the magic square $ N $ and the number of already formed pairs $ K $.
The following $ K $ lines contain the already formed pairs.

$ N $ $ K $ $ a_1 $ $ b_1 $ $ : $ $ a_K $ $ b_K $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 0

Sample Output #1

5

Sample Input #2

7 3
1 13
3 11
9 4

Sample Output #2

4

Sample Input #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

Sample Output #3

1136

Notes/Hints

Constraints

• All inputs are integers.
• $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 $ are all distinct.

Explanation

Explanation

Sample Explanation 1

The minimum complexity of the magic square is $ 0 $. There are $ 5 $ ways to pair the elements such that no lines intersect.

Sample Input 2

7 3
1 13
3 11
9 4

Sample Output 2

4

The minimum complexity is $ 2 $. There are $ 4 $ ways to achieve the complexity of $ 2 $.

Sample Input 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

Sample Output 3

1136

见题面 Input 部分

见题面 Output 部分