CF2003E2 Turtle and Inversions (Hard Version)

这是一个问题的困难版本。这个困难版本与简单版本在 $m$ 的限制条件上有所不同，而且在简单版本中，对于每一个 $i$（从 $1$ 到 $m-1$），都有 $r_i < l_{i+1}$ 的条件。只有当两个版本的问题都解决后，你才可以进行 hack。 有 $m$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$，海龟认为一个排列 $p$ 是有趣的，如果对每个区间 $l_i \le k_i < r_i$，存在一个整数 $k_i$，并且对于每个 $i$ 从 $1$ 到 $m$，满足以下条件： 设 $a_i = \max\limits_{j = l_i}^{k_i} p_j$，$b_i = \min\limits_{j = k_i + 1}^{r_i} p_j$，需满足： $$ \max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i $$ 海龟希望你找出长度为 $n$ 的所有可能的有趣排列中，逆序对数量的最大值。如果没有这样一个有趣的排列，则返回 $-1$。 排列 $p$ 中的逆序对是指满足 $p_i > p_j$ 的整数对 $(i, j)$，其中 $1 \le i < j \le n$。

输入数据包含多个测试用例。第一行给出测试用例数量 $t$（$1 \le t \le 10^3$）。接下来是每个测试用例的详细描述。 每个测试用例第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5 \cdot 10^3$, $0 \le m \le 5 \cdot 10^3$），分别表示排列的长度和区间的数量。 接下来的 $m$ 行每行两个整数 $l_i, r_i$（$1 \le l_i < r_i \le n$），表示第 $i$ 个区间。需要注意的是，可能会有相同的区间（即存在不同的 $i, j$ 使得 $l_i = l_j$ 且 $r_i = r_j$）。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^3$，$m$ 的总和不超过 $5 \cdot 10^3$。

对于每个测试用例，如果不存在有趣的排列，输出单一整数 $-1$；否则，输出最大可能逆序对的数量。 **本翻译由 AI 自动生成**

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