F. 非学术问题

时间限制：2 秒
内存限制：256 兆字节

给定一个连通的无向图，顶点编号为 $1$ 到 $n$。你的任务是最小化图中存在路径的顶点对 $(u, v)$（$1 \le u < v \le n$）的数量。为此，你可以恰好删除一条边。

找出最小的可达顶点对数量！

输入

每个测试包含多组输入数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5$，$n-1 \le m \le \min(10^5, \frac{n(n-1)}{2})$）——图中顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le 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$。