给定一个无向连通图,其顶点用从 $$$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$$$。
输出
对于每组输入数据,如果可以删除恰好一条边,则输出最小数量的可达顶点对。
示例
输入 #1
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
输出 #1
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$$$ 对可达顶点。