To address the impending STEM shortage early on, your
local elementary school decided to teach graph theory to its
kindergarten students! To tap into their age-specific skills,
the students are asked to color the vertices of a graph with
colors of their own choosing. There is one constraint, however:
they cannot use the same color for two vertices if those
vertices are connected by an edge. Furthermore, they are asked
to use as few different colors as possible. The illustration
shows a few examples of student work.
There is one problem, as you can imagine: there is no money
to train teachers to grade these students’ submissions! Thus,
your task is to write a program that computes the sample
solutions for the graphs given on each work sheet!
Input
The input consists of a description of a single graph. The
first line contains a number $N$ ($2
\le N \le 11$), the number of vertices in the graph.
Vertices are numbered $0 \ldots
N-1$. The following $N$ lines contain one or more numbers
each. The $i^{th}$ line
contains a list of vertex numbers ${ v_ j }$, denoting edges from
$v_ i$ to each
$v_ j$ in the list. You
may assume that the graph is connected (there is a path between
any two pairs of vertices).
Output
Output the minimum number of colors required to color all
vertices of the graph such that no vertices that share an edge
are colored using the same color!
The sample input corresponds to the graphs shown on the
illustration.
| Sample Input 1 |
Sample Output 1 |
4
1 2
0 2 3
0 1
1
|
3
|
| Sample Input 2 |
Sample Output 2 |
5
2 3 4
2 3 4
0 1
0 1
0 1
|
2
|
| Sample Input 3 |
Sample Output 3 |
6
1 3
0 2 4
1 5
0 4
1 3 5
2 4
|
2
|
| Sample Input 4 |
Sample Output 4 |
4
1 2 3
0 2 3
0 1 3
0 1 2
|
4
|
| Sample Input 5 |
Sample Output 5 |
5
1 2
0 2 3
0 1 4
1 4
2 3
|
3
|
