B. Хоссам и друзья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хоссам устраивает большую вечеринку, он собирается пригласить на нее своих друзей.

У него есть $$$n$$$ друзей, пронумерованных от $$$1$$$ до $$$n$$$. Они будут организованы в очередь следующим образом: $$$1, 2, 3, \ldots, n$$$.

У Хоссама есть список из $$$m$$$ пар его друзей, которые не знакомы друг с другом. Любая пара, не входящая в этот список, знакома друг с другом.

Подотрезок очереди, начинающийся с друга $$$a$$$ и заканчивающийся другом $$$b$$$, равен $$$[a, a + 1, a + 2, \ldots, b]$$$. Подоторезок очереди считается хорошим, если любая пара из этого подотрезка знакома друг с другом.

Хоссам хочешь знать, сколько пар $$$(a, b)$$$ ($$$1 \le a \le b \le n$$$), таких, что подотрезок начинающийся с друга $$$a$$$ и заканчивающийся другом $$$b$$$ хороший.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$), количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$) означающих число друзей и число пар, соответственно.

В $$$i$$$-й из следующих $$$m$$$ строк содержатся два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i\le n$$$, $$$x_i \neq y_i$$$) означающих пары друзей Хоссама, которые не знают друг друга.

Обратите внимание, что пары могут повторяться.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$, и сумма $$$m$$$ по всем наборам входных данных не первосходит$$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество хороших подотрезков.

Пример
Входные данные
2
3 2
1 3
2 3
4 2
1 2
2 3
Выходные данные
4
5
Примечание

В первом наборе ответ равен $$$4$$$. Хорошие подотрезки здесь:

[1]

[2]

[3]

[1, 2]

Во втором наборе ответ равен $$$5$$$. Хорошие подотрезки здесь:

[1]

[2]

[3]

[4]

[3, 4]