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). 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). For each test case, if there is no interesting permutation, output a single integer (-1). Otherwise, output a single integer — the max