http://poj.org/problem?id=1129
import java.util.*;
import java.io.*;
/*
*����������ŵ7��䡣��һ������ͼ��Ϊÿ����������ɫ��Ҫ���������ڵĶ�����ɫ��ͬ��
* �����ٵ���ɫ���Ƕ���?
*������������ɫ���?ֱ��ö����ɫ��+DFS������DFS�Ǳ�fö��ÿ�����ɫ���Ա��ҵ�һ����н⡣
*/
public class Main{
public static int[][] g=new int[26][26];
public static int solve(int n){
int i,j,cnum;
boolean tag=true;
// �ޱ�ͼֻ��1ɫ����
for(i=0;i< n && tag;i++){
for(j=i+1;j< n && tag;j++){
if(g[i][j]==1)
tag=false;
}
}
if(tag)
return 1;
for(cnum=2;cnum<=4;cnum++) // ö�ٴ�+dfs
{
int[] x=new int[n];
Arrays.fill(x,-1);
if(DFS(x,0,cnum,n))
return cnum;
}
return -1;
}
//DFS�ĸ��Ӷ�����ɫ��^������(4^26�����п����Լ�֦����˺ܶ��֧)
public static boolean DFS(int[] x,int vnum, int cnum,int n){
if(vnum == n) return true; // v�Ķ��㶼��ɫ�����н�
for(int i=0;i< cnum;i++){ // ���ĳ���û����ɫ�������һ��
x[vnum] = i;
if(check(vnum,x,i,n))
if(DFS(x,vnum+1,cnum,n)) // �Ϸ���ö����һ���
return true;
}
return false;
}
// �ж����ڵĶ����Ƿ���Ϳ��������ɫ
public static boolean check(int vnum,int[] x,int t,int n){
boolean find=true;
for(int i=0;i< n && find;i++){
if(g[vnum][i]==1 && x[i]==t)
find=false;
}
return find;
}
public static void main(String rgs[]) throws Exception
{
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int i,j,n=cin.nextInt();
while(n!=0){
for(i=0;i< n;i++)
Arrays.fill(g[i],0);
for(i=0;i< n;i++){
String s = cin.next();
for(j=2;j< s.length();j++)
g[i][s.charAt(j)-'A']=1;
}
int count=solve(n);
if(count==1)
System.out.println(count+" channel needed.");
else
System.out.println(count+" channels needed.");
n=cin.nextInt();
}
}
}