1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int n; 5 int a[30][30]; 6 int c[30]; 7  8 bool pd(int x,int color) 9 {10     for (int i=1;i<x;i++)11         if (a[x][i]==1 && c[i]==color) return false;12     return true;13 }14 15 bool dfs(int x,int color)16 {17     if (x>n) return true;18     for (int i=1;i<=color;i++)19         if (pd(x,i))20         {21             c[x]=i;22             return dfs(x+1,color);23         }24     return false;25 }26 int main()27 {28     scanf("%d",&n);29     while (n!=0)30     {31         memset(a,0,sizeof(a));32         for (int i=1;i<=n;i++)33         {34             char str[30];35             scanf("%s",str);36             for (int j=2;j<strlen(str);j++)37             {38                 a[str[0]-‘A‘+1][str[j]-‘A‘+1]=1;39                 a[str[j]-‘A‘+1][str[0]-‘A‘+1]=1;40             }41         }42             if (dfs(1,1)) printf("1 channel needed.\n");43             else44             {45                 for (int i=2;i<=4;i++)46                     if (dfs(1,i))47                     {48                         printf("%d channels needed.\n",i);49                         break;50                     }51             }52         scanf("%d",&n);53     }54     return 0;55 }