3575. [USACO21Feb Platinum]Minimizing Edges

【题目描述】

Bessie 有一个连通无向图 $G$。$G$ 有 $N$ 个编号为 $1\ldots N$ 的结点，以及 $M$ 条边（$2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$）。$G$ 有可能包含自环（一个结点连到自身的边），但不包含重边（连接同一对结点的多条边）。

令 $f_G(a,b)$ 为一个布尔函数，对于每一个 $1\le a\le N$ 和 $0\le b$，如果存在一条从结点 $1$ 到结点 $a$ 的路径恰好经过了 $b$ 条边，则函数值为真，否则为假。如果一条边被经过了多次，则这条边会被计算相应的次数。

Elsie 想要复制 Bessie。具体地说，她想要构造一个无向图 $G'$，使得对于所有的 $a$ 和 $b$，均有 $f_{G'}(a,b)=f_G(a,b)$。

Elsie 想要进行最少数量的工作，所以她想要构造最小可能的图。所以，你的工作是计算 $G'$ 的边数的最小可能值。

【输入格式】

输入的第一行包含 $T$，为测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $M$。

每个测试用例的以下 $M$ 行每行包含两个整数 $x$ 和 $y$（$1\le x\le y\le N$），表示 $G$ 中存在一条连接 $x$ 与 $y$ 的边。

为提高可读性，相邻的测试用例之间用一个空行隔开。

【输出格式】

对每个测试用例，输出一行，为 $G'$ 中的边数的最小可能值。

【样例输入1】

2

5 5
1 2
2 3
2 5
1 4
4 5

5 5
1 2
2 3
3 4
4 5
1 5

【样例输出1】

4
5

【样例输入输出2】

在此下载

【样例说明】

【样例 1 解释】

在样例 1 中，Elsie 可以通过从 $G$ 中移除 $(2,5)$ 来构造得到 $G'$。或者，她也可以构造一张包含以下边的图，因为她并未被限制只能从 $G$ 中移除边：

1 2
1 4
4 3
4 5

Elsie 显然不能得到比 $N-1$ 更优的解，因为 $G'$ 一定也是连通的。

【样例 2 解释】

在样例 2 这些测试用例中，Elsie 都不能做得比 Bessie 更优。

【数据规模与约定】

测试点 3 的所有测试用例满足 $N\le 5$。

测试点 4-5 的所有测试用例满足 $M=N$。

测试点 6-9 的所有测试用例中，如果并非对于所有的 $b$ 均有 $f_G(x,b)=f_G(y,b)$，则存在 $b$ 使得 $f_G(x,b)$ 为真且 $f_G(y,b)$ 为假。

测试点 10-15 中的所有测试用例满足 $N\le 10^2$。

测试点 16-20 中的测试用例没有额外限制。

每个输入包含 $T$（$1\le T\le 5\cdot 10^4$）组独立的测试用例。保证所有测试用例中的 $N$ 之和不超过 $10^5$，且所有测试用例中的 $M$ 之和不超过 $2\cdot 10^5$。

【来源】

USACO 二月公开赛 Platinum 组