E2. Черепаха и инверсии (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия этой задачи. Различия между версиями заключаются в ограничении на $$$m$$$ и условии $$$r_i < l_{i + 1}$$$, которое выполняется для каждого $$$i$$$ от $$$1$$$ до $$$m - 1$$$ в простой версии. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Черепаха дает вам $$$m$$$ отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$. Она считает, что перестановка $$$p$$$ интересна, если существуют целые числа $$$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_j$$$ для каждого целого числа $$$i$$$ от $$$1$$$ до $$$m$$$, то будет выполняться следующее условие:

$$$$$$\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 5 \cdot 10^3$$$) — длину перестановки и количество отрезков.

$$$i$$$-я из следующих $$$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$$$.

В противном случае выведите одно целое число — максимальное количество инверсий.

Пример
Входные данные
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
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]$$$.