Channel Allocation

When a radio station broadcasts over a very large area, repeaters are used to retransmit the signal so that every receiver gets a strong signal. The channel used by each repeater must be chosen carefully so that nearby repeaters do not interfere with one another. This condition is satisfied when any two adjacent repeaters use different channels.

Because the radio frequency spectrum is a scarce resource, the number of channels used by a network of repeaters should be as small as possible. Write a program that reads a description of a repeater network and determines the minimum number of channels required.

The input contains several maps of repeater networks. Each map begins with a line containing the number of repeaters. This number is between 1 and 26, and the repeaters are named by consecutive uppercase letters starting from A. For example, ten repeaters are named A, B, C, ..., I, J. A map with zero repeaters marks the end of the input.

After the number of repeaters comes the list of adjacency relations, given one line per repeater in alphabetical order. Each line has the form:

A:BCDH

which means that repeaters B, C, D and H are adjacent to repeater A. The first line describes the repeaters adjacent to A, the second those adjacent to B, and so on. If a repeater has no adjacent repeater, its line has the form:

A:

Adjacency is symmetric: if A is adjacent to B, then B is adjacent to A. Because the repeaters lie in a plane, the graph formed by the adjacency relations is planar (no two edges cross).

For each map (except the final one with zero repeaters), print one line with the minimum number of channels needed so that no two adjacent repeaters interfere. Follow exactly the format shown by the sample output. Use the singular form channel when exactly one channel is required, and the plural form channels otherwise.