#1669. 「USACO 2025.2 Gold」Friendship Editing

内存限制
512 MiB
时间限制
2000 ms
标准输入输出
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

Farmer John 的 头奶牛编号为 )。奶牛之间的朋友关系可以建模为一个有 )条边的无向图。两头奶牛为朋友当且仅当图中她们之间存在一条边。

在一次操作中,你可以添加或删除图中的一条边。计算确保以下性质成立所需的最小操作次数:如果奶牛 是朋友,则对于每头其他奶牛 中至少之一与 是朋友。

输入格式

输入的第一行包含

以下 行,每行包含一对朋友 )。每对朋友出现至多一次。

输出格式

输出你需要增加或删除的边的数量。

样例

输入 #1

3 1
1 2

输出 #1

1

输入 #2

3 2
1 2
2 3

输出 #2

0

输入 #3

4 4
1 2
1 3
1 4
2 3

输出 #3

1

数据范围与提示

样例 1 解释:

该网络不符合性质。我们可以添加边 ,或删除边 进行修复。

样例 2 解释:

不需要进行任何修改。

  • 测试点 :对于每一个 依次有一个测试点。
  • 测试点