J8 实践-11 信道分配

题目描述

当无线电台在很大范围内广播时，中继器用于重传信号，以便每个接收机都有强信号。但是，必须仔细选择每个中继器使用的信道，以便附近的中继器不会相互干扰。如果相邻中继器使用不同信道，则满足该条件。

由于射频频谱是一种宝贵的资源，因此给定的中继器网络所需的信道数量应该最小化。您必须编写一个程序来读取中继器网络的描述，并确定所需的最小信道数。

输入格式

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

在中继器数量之后是邻接关系列表。每行具有以下形式：

A： BCDH

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

A：

中继器按字母顺序排列。

注意，邻接是对称关系；如果 $A$ 与 $B$ 相邻，则 $B$ 必然与 $A$ 相邻。 输出格式

对于每个映射（除了最后一个没有中继器的映射），打印一行，其中包含所需的最小信道数，以便相邻信道不会干扰。示例输出显示了该行的格式。当只需要一个通道时，注意通道是单数形式。

样例输入

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. 

样例分析

如上所述。

数据范围

如上所述。