Friendship Editing

题目描述

农夫约翰有 $N$ 头奶牛，编号为 $1$ 到 $N$（$2\le N\le 16$）。奶牛之间的友谊关系可以建模为一个含有 $M$（$0\le M\le N(N-1)/2$）条边的无向图。两头奶牛当且仅当图中它们之间存在一条边时互为朋友。

在一次操作中，你可以向图中添加或删除一条边。请计算使得下述性质成立所需的最少操作次数：如果奶牛 $a$ 和 $b$ 是朋友，那么对于任意其他奶牛 $c$，$a$ 与 $b$ 中至少有一头与 $c$ 是朋友。

输入格式

第一行包含 $N$ 和 $M$。 接下来 $M$ 行每行包含一对朋友 $a$ 和 $b$（$1\le a<b\le N$）。 同一对朋友不会出现超过一次。

输出格式

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

3 1
1 2

1

3 2
1 2
2 3

0

4 4
1 2
1 3
1 4
2 3

1

提示

该网络不满足性质。我们可以添加边 $(2,3)$ 或 $(1,3)$ 中的一条，或者删除边 $(1,2)$ 来修复。

不需要任何修改。

SCORING: Inputs 4-13: 对于每个 $N\in [6, 15]$（按递增顺序）各有一个输入。 Inputs 14-18: $N=16$ 题目作者：Benjamin Qi

标签: USACO|2025|Gold

来源

USACO|2025|Gold