Problem B
Committee Assignment

You are the chair of a large department, and, as such, it’s your job to assign department members to committees. Everyone has to be on exactly one committee, but some department members don’t get along and cannot be assigned to the same committee. Of course, you would like to have as few committees as possible since it’s hard to make up jobs for committees you don’t really need (e.g., committee for snack machine pricing oversight, committee for shredding procurement, committee for committee name selection). What you need is a program that figures out how many committees are needed so that no mutually hostile department members are placed on the same committee.

Input

Input consists of up to $50$ department descriptions. Each begins with a positive integer $n \le 15$ and a non-negative integer $m \le n(n-1)/2$. The value of $n$ indicates the number of people there are in the department, and $m$ tells how many pairs of people don’t get along. This is followed by $m$ lines, each listing the names of two different department members who don’t get along.

A name is a sequence of up to $20$ lowercase and/or uppercase letters (a–z), and each department member has a unique name. The end of input is marked with a pair of zeros for $n$ and $m$.

Output

For each department description, print out a line giving the minimum number of committees needed to keep mutually hostile department members on different committees.

5 0
5 2
wally alice
wally dilbert
5 3
greg don
greg bill
don bill
0 0

1
2
3