#P11844. [USACO25FEB] Friendship Editing G
[USACO25FEB] Friendship Editing G
题目描述
Farmer John 的 头奶牛编号为 到 ()。奶牛之间的朋友关系可以建模为一个有 ()条边的无向图。两头奶牛为朋友当且仅当图中她们之间存在一条边。
在一次操作中,你可以添加或删除图中的一条边。计算确保以下性质成立所需的最小操作次数:如果奶牛 和 是朋友,则对于每头其他奶牛 , 和 中至少之一与 是朋友。
输入格式
输入的第一行包含 和 。
以下 行,每行包含一对朋友 和 ()。每对朋友出现至多一次。
输出格式
输出你需要增加或删除的边的数量。
3 1
1 2
1
3 2
1 2
2 3
0
4 4
1 2
1 3
1 4
2 3
1
提示
样例 1 解释:
该网络不符合性质。我们可以添加边 或 ,或删除边 进行修复。
样例 2 解释:
不需要进行任何修改。
- 测试点 :对于每一个 依次有一个测试点。
- 测试点 :。