최대 독립 집합

문제

N개의 정점과 M개의 간선으로 이루어진 무방향 그래프가 주어진다. 독립 집합은 그래프의 정점 부분집합 중 어느 두 정점도 간선으로 직접 연결되지 않은 집합을 뜻한다. 주어진 그래프에서 만들 수 있는 독립 집합의 최대 크기를 구하라.

정점의 개수가 최대 20개이므로, 비트마스크를 활용하여 모든 부분집합을 탐색하는 방식으로 해결할 수 있다.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 공백으로 구분되어 주어진다.
둘째 줄부터 M개의 줄에 걸쳐 간선의 양끝 정점 u, v가 공백으로 구분되어 주어진다.

• 1 ≤ N ≤ 20
• 0 ≤ M ≤ N(N-1)/2
• 1 ≤ u, v ≤ N (u ≠ v)
• 두 정점 사이에 여러 개의 간선이 주어지지 않는다.

출력

최대 독립 집합의 크기를 출력한다.

예제 입력 1

4 3
1 2
2 3
3 4

예제 출력 1

2

예제 입력 2

3 3
1 2
2 3
1 3

예제 출력 2

1