Friendship Editing

시간 제한2초메모리 제한2048 MB

요약

정점이 16개 이하인 그래프가 주어질 때, 모든 간선의 두 끝점이 나머지 정점을 지배하도록 만드는 최소 간선 추가/삭제 횟수를 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 완전 탐색, 비트 연산, 그래프
정답자: 아직 제출이 없습니다

문제

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$ .

입력

The first line contains $N$ and $M$ .

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

출력

The number of edges you need to add or remove.

예제3

예제 1
입력
```
3 1
1 2
```
예상 출력
```
1
```
예제 2
입력
```
3 2
1 2
2 3
```
예상 출력
```
0
```
예제 3
입력
```
4 4
1 2
1 3
1 4
2 3
```
예상 출력
```
1
```