#P11844. [USACO25FEB] Friendship Editing G

[USACO25FEB] Friendship Editing G

题目描述

Farmer John 的 NN 头奶牛编号为 11NN2N162\le N\le 16)。奶牛之间的朋友关系可以建模为一个有 MM0MN(N1)/20\le M\le N(N-1)/2)条边的无向图。两头奶牛为朋友当且仅当图中她们之间存在一条边。

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

输入格式

输入的第一行包含 NNMM

以下 MM 行,每行包含一对朋友 aabb1a<bN1\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

提示

样例 1 解释:

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

样例 2 解释:

不需要进行任何修改。

  • 测试点 4134\sim 13:对于每一个 N[6,15]N\in [6, 15] 依次有一个测试点。
  • 测试点 141814\sim 18N=16N=16