그래프 색칠

무방향 그래프에서 인접한 정점끼리 서로 다른 색이 되도록 색칠할 때 필요한 최소 색의 수를 구한다. 백트래킹을 써서 모든 경우를 탐색한다.

입력

첫째 줄에 정점 수 N과 간선 수 M이 주어진다.

다음 M개 줄에 간선의 두 정점 번호가 주어진다.

• 1 ≤ N ≤ 20
• 1 ≤ M ≤ N×(N-1)/2

출력

필요한 최소 색의 수를 출력한다.

예제 입력 1

4 6
1 2
1 3
1 4
2 3
2 4
3 4

예제 출력 1

4