CF2003E1 Turtle and Inversions (Easy Version)

This 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$$$.

Each 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 $ .

For each test case, if there is no interesting permutation, output a single integer $ -1 $ . Otherwise, output a single integer — the maximum number of inversions.

In 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] $ .