Farmer John's \(N\) cows are labeled \(1\) to \(N\) (\(2\le N\le 16\)). The friendship
relationships between the cows can be modeled as an undirected graph with \(M\)
(\(0\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 \(a\) and \(b\) are friends, then for every other cow \(c\), at least
one of \(a\) and \(b\) is friends with \(c\).

Problem credits: Benjamin Qi

SCORING

• Inputs 4-13: One input for each \(N\in [6, 15]\) in increasing order.
• Inputs 14-18: \(N=16\)

Problem credits: Benjamin Qi

The first line contains \(N\) and \(M\).

The next \(M\) lines each contain a pair of friends \(a\) and \(b\) (\(1\le a).
No pair of friends appears more than once.

The number of edges you need to add or remove.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > February > Gold