#PU1499. USACO 2025 February Contest, Gold — Problem 3. Friendship Editing

    ID: 1432 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb25来源:usaco.orgscoring:equal_test_cases枚举

USACO 2025 February Contest, Gold — Problem 3. Friendship Editing

USACO 2025 February Contest, Gold — Problem 3. Friendship Editing

题目描述

Farmer John's NN cows are labeled 11 to NN (2≤N≤162\le N\le 16). The friendship relationships between the cows can be modeled as an undirected graph with MM (0≤M≤N(N−1)/20\le M\le N(N-1)/2) edges. Two cows are friends if and only if there is an edge between them in the graph. In one operation, you can add or remove a single edge from the graph. Count the minimum number of operations required to ensure that the following property holds: If cows aa and bb are friends, then for every other cow cc, at least one of aa and bb is friends with cc.

输入格式

The first line contains NN and MM. The next MM lines each contain a pair of friends aa and bb (1≤a<b≤N1\le a<b\le N). No pair of friends appears more than once.

输出格式

The number of edges you need to add or remove.

数据范围

Inputs 4-13: One input for each N∈[6,15]N\in [6, 15] in increasing order. Inputs 14-18: N=16N=16 Problem credits: Benjamin Qi

样例

样例 1

3 1
1 2
1
The network violates the property. We can add one of edges $(2,3)$ or $(1,3)$, 
or remove edge $(1,2)$ to fix this.

样例 2

3 2
1 2
2 3
0
No changes are necessary.

样例 3

4 4
1 2
1 3
1 4
2 3
1