Turtle and Inversions (Hard Version)
Contest: Codeforces Round 968 (Div. 2)
Difficulty rating: 2700
Tags: brute force, data structures, divide and conquer, dp, greedy, math, two pointers

This is a hard 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 5 \cdot 10^3$$$) — 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. Note that there may exist identical intervals (i.e., there may exist two different indices $$$i, j$$$ such that $$$l_i = l_j$$$ and $$$r_i = r_j$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$ and the sum of $$$m$$$ 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, 3, 8, 7, 6, 2, 1, 5]$$$. In this case, we can let $$$[k_1, k_2, k_3] = [2, 2, 7]$$$.

In the fifth and the sixth test case, it can be proven that there is no interesting permutation.

In the seventh test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 6, 3, 2, 1, 5]$$$. In this case, we can let $$$[k_1, k_2, k_3, k_4] = [1, 6, 1, 6]$$$.

In the eighth test case, the interesting permutation with the maximum number of inversions is $$$[4, 7, 3, 6, 2, 5, 1]$$$.

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

Example output:
1
0
8
18
-1
-1
15
15

Editorial:
Compared to problem E1, this version contains the situation where intervals can overlap.
Consider a pair of overlapping intervals $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ (assuming $$$l_1 \le l_2$$$). The range $$$[l_1, l_2 - 1]$$$ must consist entirely of $$$0$$$s, and the range $$$[r_1 + 1, r_2]$$$ must consist entirely of $$$1$$$s. Then, you can remove the intervals $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$, add a new interval $$$[l_2, r_1]$$$, and keep track of which numbers are guaranteed to be $$$0$$$ and which are guaranteed to be $$$1$$$.
After processing in this way, the intervals will no longer overlap, reducing the problem to problem E1.
Time complexity: $$$O(n^2 + m \log m)$$$ per test case.