← 返回题目列表

Codeforces · 2003/E2

E2. 海龟和倒立(困难版)

中文机器翻译题面 查看原题

这是这个问题的困难版本。版本之间的差异在于 $$$m$$$ 和 $$$r_i < l_{i + 1}$$$ 的约束对于简单版本中从 $$$1$$$ 到 $$$m - 1$$$ 的每个 $$$i$$$ 成立。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

Turtle 为您提供 $$$m$$$ 间隔 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$。他认为如果每个区间都存在一个整数 $$$k_i$$$ ($$$l_i \le k_i < r_i$$$),并且让 $$$a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i},那么排列 $$$p$$$ 是有趣的p_j$$$ 对于从 $$$1$$$ 到 $$$m$$$ 的每个整数 $$$i$$$,以下条件成立:

$$$$$$\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i$$$$$$

Turtle 要你计算长度为 $$$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 5 \cdot 10^3$$$) — 排列的长度和间隔的数量。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$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$$$。

否则,输出一个整数——最大反转次数。

示例

输入 #1

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

输出 #1

1
0
8
18
-1
-1
15
15

注意

在第三个测试用例中,具有最大反转次数的有趣排列是 $$$[5, 2, 4, 3, 1]$$$。

在第四个测试用例中,具有最大反转次数的有趣排列是 $$$[4, 3, 8, 7, 6, 2, 1, 5]$$$。在这种情况下,我们可以让 $$$[k_1, k_2, k_3] = [2, 2, 7]$$$。

在第五和第六个测试用例中,可以证明不存在有趣的排列。

在第七个测试用例中,具有最大反转次数的有趣排列是 $$$[4, 7, 6, 3, 2, 1, 5]$$$。在这种情况下,我们可以让 $$$[k_1, k_2, k_3, k_4] = [1, 6, 1, 6]$$$。

在第八个测试用例中,具有最大反转次数的有趣排列是 $$$[4, 7, 3, 6, 2, 5, 1]$$$。