重点单词：

broadcast v.散布，传播，广播， n.电视节目，广播节目；

allocate v.分配， 分派， 划拨。

singular adj.单数的，突出的，独特的。

format n.计划， 设计， 安排 v.格式化， 排版

segment v.划分， 分割, 分裂；n.部分 片段。

symmetric adj.对称的.

retransmit v.重新发送， 中继 ，转播；
upper case n.大写字母；

出处：https://acs.jxnu.edu.cn/problem/NOIOPJCH0205131

Channel Allocation

 1000ms  65536K

描述：

When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels. 当一个无线电台在很大范围内广播时，中继器被用来重新传输信号，这样每个接收器都有一个强信号。但是，必须仔细选择每个中继器使用的信道，以便附近的中继器不会相互干扰。如果相邻中继器使用不同的信道，则满足该条件。

Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required. 由于无线电频谱是一种宝贵的资源，给定的中继器网络所需的信道数量应该最小化。您必须编写一个程序，读入中继器网络的描述，并确定所需的最小通道数。

输入：

The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,...,I and J. A network with zero repeaters indicates the end of input.

 

Following the number of repeaters is a list of adjacency relationships. Each line has the form:

A:BCDH

which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form

A:
The repeaters are listed in alphabetical order.

输入由多个转发器网络图组成。每个地图都以一行开始，其中包含转发器的数量。这介于1和26之间，中继器由字母表中以A开头的连续大写字母表示。例如，10个中继器的名称为A、B、C、，。。。，I和J。具有零中继器的网络表示输入结束。

在中继器的数量后面是一个邻接关系列表。每一行的形式如下：

A：BCDH

这表示中继器B、C、D和H与中继器A相邻。第一行描述与中继器A相邻的中继器，第二行描述与B相邻的中继器，依此类推。如果中继器与任何其他中继器不相邻，则其线路具有以下形式：

A:

中继器按字母顺序排列。

Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross. 注意，邻接是一种对称关系；如果A与B相邻，则B必然与A相邻。此外，由于中继器位于一个平面上，因此通过连接相邻中继器形成的图形没有任何相交的线段。

输出：

For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required. 对于每个图（除了最后一个没有中继器的图），打印一行，其中包含所需的最小通道数，以便相邻通道不会干扰。示例输出显示了此行的格式。当只需要一个通道时，请注意通道为单数形式。

样例输入：

2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0

样例输出：

1 channel needed.
3 channels needed.
4 channels needed. 

注释：

Source: Southern African 2001