#PU1499. USACO 2025 February Contest, Gold — Problem 3. Friendship Editing
USACO 2025 February Contest, Gold — Problem 3. Friendship Editing
USACO 2025 February Contest, Gold — Problem 3. Friendship Editing
题目描述
Farmer John's cows are labeled to (). The friendship relationships between the cows can be modeled as an undirected graph with () 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 and are friends, then for every other cow , at least one of and is friends with .
输入格式
The first line contains and . The next lines each contain a pair of friends and (). 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 in increasing order. Inputs 14-18: 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