C. Джерри и Том
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джерри и Том играют в игру на ориентированном графе $$$G$$$ с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Для каждой вершины $$$1 \le u \lt n$$$ существует направленное ребро от $$$u$$$ к $$$u+1$$$. Кроме того, есть $$$m$$$ дополнительных направленных рёбер. $$$i$$$-е дополнительное ребро идет от $$$u_i$$$ к $$$v_i$$$, где $$$1 \le u_i \lt v_i \le n$$$.

Граф $$$G$$$ имеет следующее особое свойство: не существует двух рёбер $$$(u_i\to v_i)$$$ и $$$(u_j\to v_j)$$$ таких, что $$$u_i \lt u_j \lt v_i \lt v_j$$$.

В начале игры Джерри и Том стоят на вершинах $$$x$$$ и $$$y$$$ соответственно, где $$$x \ne y$$$. Игроки ходят по очереди. На каждом ходу игроки действуют согласно следующим правилам, при этом Джерри ходит первым, затем Том:

  • Джерри должен выбрать одно исходящее ребро из своей текущей вершины и переместиться по нему до конца. Если у его текущей вершины нет исходящих рёбер, он остается на месте.
  • Том может выбрать одно исходящее ребро из своей текущей вершины и переместиться по нему до конца, или выбрать не двигаться и остаться на месте.

Если в конце любого хода Джерри и Том находятся на одной и той же вершине (включая вершину $$$n$$$), игра немедленно заканчивается, и Том побеждает. В противном случае, если Джерри изначально находится на вершине $$$n$$$ или достигает вершины $$$n$$$ в конце любого хода, побеждает Джерри.

Обратите внимание, что если после хода Джерри и Том оба находятся на вершине $$$n$$$, то Том выигрывает.

В течение всей игры оба игрока знают позиции друг друга.

Можно доказать, что игра закончится за конечное число ходов.

Для пары целых чисел $$$1 \le x,y \le n$$$, $$$x \ne y$$$, определим $$$f(x,y)$$$ следующим образом:

  • Джерри и Том будут играть в игру, где Джерри начинает на вершине $$$x$$$, а Том начинает на вершине $$$y$$$. Том хочет победить, но он также хочет минимизировать количество раз, когда он действительно двигается (то есть количество ходов, в которых он меняет свою вершину; ход "остаться на месте" не считается движением). Предполагая, что оба игрока играют оптимально, пусть $$$f(x,y)=0$$$, если Том не может выиграть; в противном случае пусть $$$f(x,y)$$$ будет минимальным количеством движений, которые Том должен сделать, чтобы обеспечить победу. Если Том выигрывает при оптимальной игре, Джерри все равно пытается максимизировать количество ходов, необходимое Тому для победы.

Вычислите $$$$$$\sum\limits_{1 \le x,y \le n, x \ne y}f(x,y).$$$$$$

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

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

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

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i + 1 \lt v_i$$$), представляющих дополнительное ребро. Гарантируется, что для любой упорядоченной пары вершин $$$(u,v)$$$ существует не более одного ребра от $$$u$$$ к $$$v$$$. Гарантируется, что не существует двух рёбер $$$(u_i\to v_i)$$$ и $$$(u_j\to v_j)$$$ таких, что $$$u_i \lt u_j \lt v_i \lt v_j$$$.

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

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

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

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

В первом наборе входных данных:

  • $$$x=1$$$, $$$y=2$$$: Джерри вынужден переместиться в $$$2$$$ на первом ходу. Том может ждать на $$$2$$$ в первом ходу. Таким образом, в конце первого хода и Том, и Джерри находятся в $$$2$$$, $$$f(1,2)=0$$$, так как Том может выиграть, не делая ни одного хода.
  • $$$x=2$$$, $$$y=1$$$: Джерри находится на $$$n=2$$$ в начале; Том не может выиграть. Таким образом, $$$f(2,1)=0$$$.

В третьем наборе входных данных пары $$$(x,y)$$$, при которых Том выигрывает, следующие:

  • Для $$$x=1,2,3$$$ и $$$y=4$$$ независимо от ходов Джерри Том может оставаться в $$$4$$$ до тех пор пока Джерри не достигнет $$$4$$$. Тому выигрывает, не двигаясь; $$$f(1,4)=f(2,4)=f(3,4)=0$$$.
  • Для $$$x=1,2$$$ и $$$y=3$$$ независимо от первого хода Джерри Тому нужно переместиться на $$$4$$$ на первом ходу, чтобы гарантировать победу. Например, если Джерри начинает в $$$1$$$ и двигается в $$$4$$$ по ребру $$$(1 \to 4)$$$, а Том решит остаться в $$$3$$$ на первом ходу, Джерри достигнет $$$4$$$ в конце первого хода, выигрывая игру. $$$f(1,3)=f(2,3)=1$$$.
  • Для $$$x=1,3$$$ и $$$y=2$$$ Тому также нужно переместиться на $$$4$$$ на первом ходу, чтобы гарантировать победу; $$$f(1,2)=f(3,2)=1$$$.
  • Для $$$x=2,3$$$ и $$$y=1$$$ Тому все еще нужно переместиться на $$$4$$$ на первом ходу, чтобы гарантировать победу; $$$f(2,1)=f(3,1)=1$$$.