G. Просто добавь ребро
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан ориентированный ациклический граф из $$$n$$$ вершин и $$$m$$$ ребер. Для всех ребер графа $$$a \to b$$$ выполняется $$$a < b$$$.

Вам нужно найти количество пар вершин $$$x$$$, $$$y$$$ таких, что $$$x > y$$$, и после добавления в граф ребра $$$x \to y$$$ в нем будет существовать гамильтонов путь.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 5$$$): количество наборов входных данных.

Следующие строки содержат описания наборов входных данных.

В первой строке находятся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 150\,000$$$, $$$0 \leq m \leq \min(150\,000, \frac{n(n-1)}{2})$$$): количество вершин и ребер в графе.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$a$$$ и $$$b$$$ ($$$1 \leq a < b \leq n$$$), описывающих ребро графа $$$a \to b$$$. Никакое ребро $$$a \to b$$$ не встречается более одного раза.

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

Для каждого набора входных данных выведите одно целое число: количество пар вершин $$$x$$$, $$$y$$$, $$$x > y$$$, таких, что после добавления в граф ребра $$$x \to y$$$ в графе найдется гамильтонов путь.

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

В первом примере любое ребро $$$x \to y$$$ такое, что $$$x > y$$$, подойдет, т. к. уже существует путь $$$1 \to 2 \to 3$$$.

Во втором примере подходит только ребро $$$4 \to 1$$$. Если его добавить, появится путь $$$3 \to 4 \to 1 \to 2$$$.

В третьем примере можно добавить ребра $$$2 \to 1$$$, $$$3 \to 1$$$, $$$4 \to 1$$$, $$$4 \to 2$$$.