Friendship Editing
Farmer John's N cows are labeled 1 to N (2≤N≤16). The friendship relationships between the cows can be modeled as an undirected graph with M (0≤M≤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.
The network violates the property. We can add one of edges (2,3) or (1,3), or remove edge (1,2) to fix this.
No changes are necessary.
SCORING:
- Inputs 4-13: One input for each N∈[6,15] in increasing order.
- Inputs 14-18: N=16
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first line contains N and M.
The next M lines each contain a pair of friends a and b (1≤a<b≤N). No pair of friends appears more than once.
Output Format
The number of edges you need to add or remove.