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

Вам дан связный неориентированный граф, вершины которого пронумерованы целыми числами от $$$1$$$ до $$$n$$$. Ваша задача минимизировать количество пар вершин $$$1 \leq u < v \leq n$$$, между которыми существует путь в этом графе. Для этого вы можете удалить ровно одно любое ребро из графа.

Найдите это наименьшее количество пар вершин!

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq \min(10^5, \frac{n \cdot (n - 1)}{2})$$$) — количество вершин в графе и количество ребер.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n, u \neq v$$$), означающих, что в графе есть неориентированное ребро между вершинами $$$u$$$ и $$$v$$$.

Гарантируется, что данный граф связный и без кратных ребер.

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

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

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

Пример
Входные данные
6
2 1
1 2
3 3
1 2
2 3
1 3
5 5
1 2
1 3
3 4
4 5
5 3
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
5 5
1 2
1 3
2 3
2 4
3 5
10 12
1 2
1 3
2 3
2 4
4 5
5 6
6 7
7 4
3 8
8 9
9 10
10 8
Выходные данные
0
3
4
6
6
21
Примечание

В первом наборе входных данных мы удалим единственное ребро $$$(1, 2)$$$ и единственная пара вершин $$$(1, 2)$$$ станет не достижима друг из друга.

Во втором наборе входных данных какое бы ребро мы не удалили, все вершины будут достижимы друг из друга.

В четвертом наборе входных данных так выглядит граф изначально.

Мы удалим ребро $$$(3, 4)$$$ и тогда достижимы друг из друга будут только пары вершин $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$, $$$(5, 6)$$$.

В шестом наборе входных данных так выглядит граф изначально.

После удаления ребра $$$(2, 4)$$$ граф будет выглядеть следующим образом. Таким образом, будет $$$21$$$ пара достижимых друг из друга вершин.