← 返回题目列表

Codeforces · 1986/F

F. 非学术问题

中文机器翻译题面 查看原题

给定一个无向连通图,其顶点用从 $$$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$$$ 对可达顶点。