1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 int n,map[26][26];
 5 int vis[26][4];//vis[i][j]表示第i个节点被染第j种颜色；
 6 int ans;
 7 
 8 void cmp()
 9 {
10     int res = -1;
11     for(int i = 0; i < 4; i++)
12     {
13         for(int j = 0; j < n; j++)
14             if(vis[j][i] && res < i)
15                 res = i;
16     }
17     if(ans > res)
18         ans = res;
19 }
20 void dfs(int x)
21 {
22     if(x >= n)
23     {
24         cmp();
25         return;
26     }
27     for(int i = 0; i < 4; i++)
28     {
29         bool flag = true;
30         for(int j = 0; j < n; j++)
31         {
32             //如果节点x的前驱或后继已经染了第i种色，节点x就不能染i色；
33             if((map[j][x]&&vis[j][i])||(map[x][j]&&vis[j][i]))
34             {
35                 flag = false;
36                 break;
37             }
38         }
39         if(flag)
40         {
41             vis[x][i] = 1;//不满足上个条件，节点x染i色；
42             dfs(x+1);//继续染下一个节点；
43             vis[x][i] = 0;
44         }
45     }
46 }
47 int main()
48 {
49     char s[30];
50     while(~scanf("%d",&n) && n)
51     {
52         memset(map,0,sizeof(map));
53         memset(vis,0,sizeof(vis));
54         for(int i = 0; i < n; i++)
55         {
56             scanf("%s",s);
57             int u = s[0]-'A';
58             for(int j = 2; s[j]; j++)
59             {
60                 int v = s[j]-'A';
61                 map[u][v] = 1;
62             }
63         }
64         ans = 5;
65         vis[0][0] = 1;//假设第一个节点已染第一个色
66         dfs(1);//从第二个节点开始染色；
67         ans += 1;
68         if(ans == 1)
69             printf("1 channel needed.\n");
70         else
71             printf("%d channels needed.\n",ans);
72     }
73     return 0;
74 }