CF2003E1.Turtle and Inversions (Easy Version)

这是题目的简化版本。这两种题目的区别在于对于 $m$ 的限制及在简化版本中，满足 $r_i < l_{i + 1}$ 对于每个 $i$ 从 $1$ 到 $m-1$。只有当两个版本的问题都被解决后，才可以进行 hack。

海龟给了你 $m$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$。他认为一个排列 $p$ 是有趣的，如果对于每个区间存在一个整数 $k_i$ 满足 $l_i \le k_i < r_i$，那么对于每个从 $1$ 到 $m$ 的整数 $i$，可以计算出 $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$ 的所有有趣排列中能获得的最大逆序对数量，或者告诉他是否没有这样的有趣排列。

排列 $p$ 的逆序对是指任意两个整数对 $(i, j)$（$1 \le i < j \le n$）且满足 $p_i > p_j$。

每组数据包含多个测试用例。第一行是测试用例的数量 $t$（$1 \le t \le 10^3$）。每个测试用例的描述如下。

对于每个测试用例，第一行有两个整数 $n, m$（$2 \le n \le 5 \cdot 10^3, 0 \le m \le \frac{n}{2}$），分别表示排列的长度和区间的数量。

接下来的 $m$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i < r_i \le n$），表示第 $i$ 个区间。

注意：本版本输入确保 $r_i < l_{i + 1}$ 对于每个从 $1$ 到 $m-1$ 的 $i$。

所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^3$。

对于每个测试用例，如果没有有趣的排列，输出 $-1$。否则，输出一个整数，表示最大逆序对的数量。

在第三个测试用例中，最大逆序对数量的有趣排列是 $[5, 2, 4, 3, 1]$。

在第四个测试用例中，最大逆序对数量的有趣排列是 $[4, 8, 7, 6, 3, 2, 1, 5]$。这时可以设定 $[k_1, k_2] = [1, 7]$。

在第五个测试用例中，最大逆序对数量的有趣排列是 $[4, 7, 6, 3, 2, 1, 5]$。

在第六个测试用例中，最大逆序对数量的有趣排列是 $[4, 7, 3, 6, 2, 5, 1]$。

本翻译由 AI 自动生成