Problems
Farmer John's N cows are labeled from 1 to N (2 ≤ N ≤ 16). The friendship relationships among the cows can be modeled as an undirected graph with M edges (0 ≤ M ≤ N(N−1)/2). Two cows are friends if and only if there is an edge between them.
In one operation, you can add or remove a single edge from the graph. Your task is to count the minimum number of operations required so that the following property holds: If cows a and b are friends, then for every other cow c, at least one of a or b is friends with c.
Input
The first line contains two integers N and M.
The next M lines each contain two integers a and b (1 ≤ a < b ≤ N), representing that cows a and b are friends. No pair of friends appears more than once.
Output
Output a single integer representing the minimum number of edges you need to add or remove to satisfy the property.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 50 | One input for each N∈[6,15] in increasing order |
| #2 | 50 | |
Example #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.
Example #2
3 2
1 2
2 3
0
No changes are necessary.
Example #3
4 4
1 2
1 3
1 4
2 3
1
Only one operation is needed to adjust the network so that it meets the required property.
You must sign in to write code.