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 自动生成