A6420. 「USACO 2021.2 Platinum」Minimizing Edges
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目来自 [USACO 2021 February Contest, Platinum](http://usaco.org/index.php?page=feb21results) Problem 2. [Minimizing Edges](http://usaco.org/index.php?page=viewproblem2&cpid=1117&lang=zh)。**
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$（$1\le T\le 5\cdot 10^4$）组独立的测试用例。保证所有测试用例中的 $N$ 之和不超过 $10^5$，且所有测试用例中的 $M$ 之和不超过 $2\cdot 10^5$。
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$（$1\le T\le 5\cdot 10^4$）组独立的测试用例。保证所有测试用例中的 $N$ 之和不超过 $10^5$，且所有测试用例中的 $M$ 之和不超过 $2\cdot 10^5$。
输入格式
输入的第一行包含 $T$，为测试用例的数量。
每个测试用例的第一行包含两个整数 $N$ 和 $M$。
每个测试用例的以下 $M$ 行每行包含两个整数 $x$ 和 $y$（$1\le x\le y\le N$），表示 $G$ 中存在一条连接 $x$ 与 $y$ 的边。
为提高可读性，相邻的测试用例之间用一个空行隔开。
每个测试用例的第一行包含两个整数 $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
7 8 10 1 2 1 3 1 4 1 5 2 6 3 7 4 8 5 8 6 7 8 8 10 11 1 2 1 5 1 6 2 3 3 4 4 5 4 10 6 7 7 8 8 9 9 9 13 15 1 2 1 5 1 6 2 3 3 4 4 5 6 7 7 8 7 11 8 9 9 10 10 11 11 12 11 13 12 13 16 18 1 2 1 7 1 8 2 3 3 4 4 5 5 6 6 7 8 9 9 10 9 15 9 16 10 11 11 12 12 13 13 14 14 15 14 16 21 22 1 2 1 9 1 12 2 3 3 4 4 5 5 6 6 7 7 8 7 11 8 9 8 10 12 13 13 14 13 21 14 15 15 16 16 17 17 18 18 19 19 20 20 21 20 26 1 2 1 5 1 6 2 3 3 4 4 5 4 7 6 8 8 9 8 11 8 12 8 13 8 14 8 15 8 16 8 17 9 10 10 18 11 18 12 19 13 20 14 20 15 20 16 20 17 20 19 20 24 31 1 2 1 7 1 8 2 3 3 4 4 5 5 6 6 7 6 9 8 10 10 11 10 16 10 17 10 18 10 19 10 20 11 12 12 13 13 14 14 15 15 16 15 17 15 18 15 19 15 20 15 21 15 22 15 23 15 24 21 22 23 24
输出 #2
10 11 15 18 22 26 31
说明/提示
- 测试点 $3$ 的所有测试用例满足 $N\le 5$。
- 测试点 $4\sim 5$ 的所有测试用例满足 $M=N$。
- 测试点 $6\sim 9$ 的所有测试用例中，如果并非对于所有的 $b$ 均有 $f_G(x,b)=f_G(y,b)$，则存在 $b$ 使得 $f_G(x,b)$ 为真且 $f_G(y,b)$ 为假。
- 测试点 $10\sim 15$ 中的所有测试用例满足 $N\le 10^2$。
- 测试点 $16\sim 20$ 中的测试用例没有额外限制。
- 测试点 $4\sim 5$ 的所有测试用例满足 $M=N$。
- 测试点 $6\sim 9$ 的所有测试用例中，如果并非对于所有的 $b$ 均有 $f_G(x,b)=f_G(y,b)$，则存在 $b$ 使得 $f_G(x,b)$ 为真且 $f_G(y,b)$ 为假。
- 测试点 $10\sim 15$ 中的所有测试用例满足 $N\le 10^2$。
- 测试点 $16\sim 20$ 中的测试用例没有额外限制。