문제
농부 John의 N마리 소들은 1부터 N까지 번호가 매겨져 있으며 (2 ≤ N ≤ 16), 소들 간의 우정 관계는 M개의 간선(0 ≤ M ≤ N(N−1)/2)을 가진 무방향 그래프로 표현됩니다. 두 소가 친구라는 것은 두 소 사이에 간선이 존재할 때만 성립합니다.
한 번의 연산으로, 그래프에 간선을 하나 추가하거나 제거할 수 있습니다. 목표는 다음 조건을 만족하도록 만드는 최소 연산 횟수를 구하는 것입니다:
만약 소 a와 소 b가 친구라면, a와 b 각각 중 적어도 한 소가 (a, b를 제외한) 모든 다른 소 c와 친구여야 한다.
입력
첫 번째 줄에 두 정수 N과 M이 주어집니다.
이후 M개의 줄 각각에, 두 소의 번호 a와 b (1 ≤ a < b ≤ N)가 공백으로 구분되어 주어집니다. (어떤 친구 쌍도 중복되지 않습니다.)
출력
조건을 만족하도록 만들기 위해 추가하거나 제거해야 하는 간선의 최소 개수를 한 줄에 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 50점 | 각 입력은 N ∈ [6,15]에 대해 한 개씩 주어집니다 |
| #2 | 50점 | |
예제1
입력
3 1
1 2
출력
1
네트워크가 조건을 위반합니다. (예를 들어, (1,2) 간선만 존재하는 경우, 3번 소와의 관계가 없으므로 문제가 발생합니다.) 이를 해결하기 위해 (2,3) 또는 (1,3) 간선을 추가하거나, (1,2) 간선을 제거할 수 있으며, 최소 연산 횟수는 1입니다.
예제2
입력
3 2
1 2
2 3
출력
0
네트워크는 이미 조건을 만족하므로, 변경할 필요가 없습니다.
예제3
입력
4 4
1 2
1 3
1 4
2 3
출력
1
최소 1회의 연산으로 네트워크를 조건에 맞게 수정할 수 있습니다.
출처
USACO 2025 February Gold