E1. Turtle and Inversions (Easy Version)time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is an easy version of this problem. The differences between the versions are the constraint on $$$m$$$ and $$$r_i < l_{i + 1}$$$ holds for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$ in the easy version. You can make hacks only if both versions of the problem are solved.Turtle gives you $$$m$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$. He thinks that a permutation $$$p$$$ is interesting if there exists an integer $$$k_i$$$ for every interval ($$$l_i \le k_i < r_i$$$), and if he lets $$$a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i} p_j$$$ for every integer $$$i$$$ from $$$1$$$ to $$$m$$$, the following condition holds:$$$$$$\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i$$$$$$Turtle wants you to calculate the maximum number of inversions of all interesting permutations of length $$$n$$$, or tell him if there is no interesting permutation.An inversion of a permutation $$$p$$$ is a pair of integers $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) such that $$$p_i > p_j$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n, m$$$ ($$$2 \le n \le 5 \cdot 10^3, 0 \le m \le \frac{n}{2}$$$) — the length of the permutation and the number of intervals.The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$l_i, r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — the $$$i$$$-th interval.Additional constraint on the input in this version: $$$r_i < l_{i + 1}$$$ holds for each $$$i$$$ from $$$1$$$ to $$$m - 1$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.OutputFor each test case, if there is no interesting permutation, output a single integer $$$-1$$$.Otherwise, output a single integer — the maximum number of inversions.ExampleInput62 02 11 25 12 48 21 46 87 21 34 77 31 23 45 6Output1
0
8
21
15
15
NoteIn the third test case, the interesting permutation with the maximum number of inversions is $$$[5, 2, 4, 3, 1]$$$.In the fourth test case, the interesting permutation with the maximum number of inversions is $$$[4, 8, 7, 6, 3, 2, 1, 5]$$$. In this case, we can let $$$[k_1, k_2] = [1, 7]$$$.In the fifth test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 6, 3, 2, 1, 5]$$$.In the sixth test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 3, 6, 2, 5, 1]$$$.