그래프 색칠하기

시간 제한6초메모리 제한1024 MB

요약

연결된 그래프에서 인접한 정점끼리 다른 색이 되도록 칠할 때 필요한 최소 색의 개수를 구합니다. 정점은 최대 11개입니다.

난이도: 보통10점 중 4점
유형: 그래프, 백트래킹, 완전 탐색
정답자: 아직 제출이 없습니다

문제

머지않아 닥칠 STEM 인력 부족에 대비하려고 동네 초등학교가 유치원생들에게 그래프 이론을 가르치기로 했다. 아이들의 나이에 맞는 능력을 활용하기 위해, 아이들은 그래프의 정점을 자기가 고른 색으로 칠하게 된다. 다만 조건이 하나 있다. 간선으로 이어진 두 정점에는 같은 색을 쓸 수 없다. 또한 사용하는 색의 종류는 가능한 한 적어야 한다. 그림에는 학생들이 낸 결과물의 예가 몇 개 나와 있다.

짐작하겠지만 문제가 하나 있다. 학생들의 답안을 채점할 교사를 훈련할 돈이 없다. 그래서 각 학습지에 주어진 그래프의 모범 답안을 계산하는 프로그램을 작성해야 한다.

입력

입력은 그래프 하나에 대한 설명이다. 첫 줄에는 정점의 개수 $N$ ( $2 \le N \le 11$ )이 주어진다. 정점은 $0 \ldots N-1$ 번으로 번호가 매겨져 있다. 이어지는 $N$ 개의 줄에는 각각 하나 이상의 정수가 주어진다. $i$ 번째 줄에는 정점 $v_i$ 에서 나가는 간선의 도착 정점 번호 ${ v_j }$ 가 적혀 있다. 그래프가 연결되어 있다고 가정해도 된다(임의의 두 정점 사이에 경로가 있다).

출력

그래프의 모든 정점을 칠하는 데 필요한 색의 최소 개수를 출력한다. 간선으로 이어진 두 정점은 같은 색으로 칠해져서는 안 된다.

예제5

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