Turtle and Inversions (Easy Version)
Contest: Codeforces Round 968 (Div. 2)
Difficulty rating: 2600
Tags: brute force, divide and conquer, dp, greedy, math

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

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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]$$$.

Example input:
6
2 0
2 1
1 2
5 1
2 4
8 2
1 4
6 8
7 2
1 3
4 7
7 3
1 2
3 4
5 6

Example output:
1
0
8
21
15
15

Editorial:
Divide all numbers into two types: small numbers ($$$0$$$) and large numbers ($$$1$$$), such that any small number is less than any large number. In this way, a permutation can be transformed into a $$$01$$$ sequence.
A permutation is interesting if and only if there exists a way to divide all numbers into two types such that, for every given interval $$$[l, r]$$$, all $$$0$$$s appear before all $$$1$$$s, and there is at least one $$$0$$$ and one $$$1$$$ in the interval. Such a $$$01$$$ sequence is called interesting.
If an interesting $$$01$$$ sequence is fixed, we can greedily arrange all $$$0$$$s in descending order and all $$$1$$$s in descending order. Let the number of $$$0$$$s be $$$x$$$ and the number of $$$1$$$s be $$$y$$$. Let $$$z$$$ be the number of index pairs $$$(i, j)$$$, where the $$$i$$$-th number is $$$1$$$ and the $$$j$$$-th number is $$$0$$$ (such pairs are called $$$10$$$ pairs). Then, the maximum number of inversions is $$$\frac{x(x - 1)}{2} + \frac{y(y - 1)}{2} + z$$$.
In this version, the intervals are non-overlapping, so DP can be applied directly. Let $$$f_{i, j}$$$ represent the maximum number of $$$10$$$ pairs when considering all numbers from $$$1$$$ to $$$i$$$, where there are $$$j$$$ $$$1$$$s. For transitions, if $$$i$$$ is the left endpoint of an interval and the right endpoint of this interval is $$$p$$$, we can enumerate the number of $$$0$$$s as $$$k$$$ and the number of $$$1$$$s as $$$p - i + 1 - k$$$ for the transition. Otherwise, we consider whether $$$i$$$ is $$$0$$$ or $$$1$$$.
The answer is $$$\max\limits_{i = 0}^n f_{n, i} + \frac{i(i - 1)}{2} + \frac{(n - i)(n - i - 1)}{2}$$$.
Time complexity: $$$O(n^2 + m)$$$ per test case.