当一个广播站向一个很广的地区广播时需要使用中继器，用来转发信号，使得接收器都能接收到足够强的信号。然而，每个中继器所使用的频道必须很好地选择，以保证相邻的中继器不会互相干扰。要满足这个条件，相邻中继器必须使用不同的频道。 由于广播频率带宽是一种很宝贵的资源，对于一个给定的中继器网络，所使用频道数量应该尽可能少。编写程序，读入中继器网络的信息，计算需要使用频道的最少数目。

输入文件包含多个测试数据，每个测试数据描述了一个中继器网络，格式如下。 (1) 第1行为整数N (1≤N≤26)，表示中继器的数目，中继器用前N个大写字母表示，例如，假设有10个中继器，则这10个中继器的名字为A, B, C, …, J。 (2) 接下来有N行，描述了这N个中继器的相邻关系，第1行描述和中继器A相邻的中继器，第2行描述和中继器B相邻的中继器，以此类推。每行的格式为“A:BCDH”，表示和中继器A相邻的中继器有B、C、D和H(按字母升序排列)。如果一个中继器没有相邻中继器，则其格式为“A:”。 注意，相邻关系是对称的，A与B相邻，则B也与A相邻；另外，中继器网络是一个平面图，即中继器网络所构成的图中不存在相交的边。 输入文件的最后一行为N = 0，表示输入结束。

对每个中继器网络，输出一行，为该中继器网络所需频道的最小数目。