問題文

円周上に N 個の点があり、時計回りに 1, 2, \ldots, N と番号づけられています。 また、M 本の線分があり、線分 i は点 L_i と点 R_i を結んでいます。

線分 s,t が端点以外で交わるような、(s,t) (1 \leq s \lt t \leq M) の組の数を求めてください。

制約

• 3\leq N\leq 300000
• 2\leq M\leq 300000
• 1\leq L_i < R_i\leq N
• (L_i, R_i) \neq (L_j, R_j) (1 \leq i \lt j \leq M)

小課題

1. (1 点) N \leq 1000, M \leq 1000
2. (2 点) N \leq 1000, M \leq 100000
3. (4 点) 追加の制約はない

入力例 1

6 3
2 5
1 4
1 3

出力例 1

2

入力例 2

250 10
13 218
17 99
24 180
53 115
96 97
111 158
124 164
135 227
158 177
204 224

出力例 2

10

入力例 3

100 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11

出力例 3

0

入力例 4

100 10
1 100
2 99
3 98
4 97
5 96
6 95
7 94
8 93
9 92
10 91

出力例 4

0

入力例 5

1000 40
12 43
23 59
32 118
44 751
68 136
70 168
85 328
88 809
92 981
95 540
98 772
98 903
125 896
173 737
199 325
212 369
227 587
230 374
287 442
306 926
314 858
316 371
318 493
337 506
384 887
387 493
394 457
404 652
414 527
422 920
441 730
445 620
468 602
482 676
568 857
587 966
653 757
710 928
764 927
778 916

出力例 5

229