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 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$.

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

Sample Input 1 | Sample Output 1 |
---|---|

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