loj#P3482. 「USACO 2021.2 Platinum」Minimizing Edges
「USACO 2021.2 Platinum」Minimizing Edges
题目描述
题目来自 USACO 2021 February Contest, Platinum Problem 2. Minimizing Edges。
Bessie 有一个连通无向图 。 有 个编号为 的结点,以及 条边()。 有可能包含自环(一个结点连到自身的边),但不包含重边(连接同一对结点的多条边)。
令 为一个布尔函数,对于每一个 和 ,如果存在一条从结点 到结点 的路径恰好经过了 条边,则函数值为真,否则为假。如果一条边被经过了多次,则这条边会被计算相应的次数。
Elsie 想要复制 Bessie。具体地说,她想要构造一个无向图 ,使得对于所有的 和 ,均有 。
Elsie 想要进行最少数量的工作,所以她想要构造最小可能的图。所以,你的工作是计算 的边数的最小可能值。
每个输入包含 ()组独立的测试用例。保证所有测试用例中的 之和不超过 ,且所有测试用例中的 之和不超过 。
输入格式
输入的第一行包含 ,为测试用例的数量。
每个测试用例的第一行包含两个整数 和 。
每个测试用例的以下 行每行包含两个整数 和 (),表示 中存在一条连接 与 的边。
为提高可读性,相邻的测试用例之间用一个空行隔开。
输出格式
对每个测试用例,输出一行,为 中的边数的最小可能值。
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
4
5
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
10
11
15
18
22
26
31
数据范围与提示
- 测试点 的所有测试用例满足 。
- 测试点 的所有测试用例满足 。
- 测试点 的所有测试用例中,如果并非对于所有的 均有 ,则存在 使得 为真且 为假。
- 测试点 中的所有测试用例满足 。
- 测试点 中的测试用例没有额外限制。