//import java.util.Scanner;
//
//
//public class search {
//	static boolean[][] paths;
//	static boolean[][][] pathstraveled;
//	public static int minsolution;
//	static int nodesvisited;
//	static int[] timesvisited;
//	public static void main(String[] args)
//	{
//		Scanner in = new Scanner(System.in);
//		int sites,officers,pathnum;
//		while((sites=in.nextInt())!=0)
//		{
//			officers = in.nextInt();
//			pathnum = in.nextInt();
//			minsolution = Integer.MAX_VALUE;
//			paths = new boolean[sites][sites];
//			pathstraveled = new boolean[officers][sites][sites];
//			timesvisited = new int[sites];
//			for(int i=0;i<pathnum;i++)
//			{
//				String path = in.next();
//				paths[path.charAt(0)-'A'][path.charAt(1)-'A'] = true;
//				paths[path.charAt(1)-'A'][path.charAt(0)-'A'] = true;
//			}
////			System.out.println("Starting traversal");
//			traverse(0,0,0,0);
//			System.out.println(minsolution);
//		}
//	}
//	public static void traverse(int node,int officer,int distance,int maxdistance)
//	{//System.out.println("START TRAVERSE: "+node+" "+officer+" "+distance+" "+maxdistance);
//		if(timesvisited[node]==0)
//			nodesvisited++;
//		timesvisited[node]++;
//		if(nodesvisited==paths.length)
//		{
//			minsolution=Math.min(minsolution,maxdistance);
//			timesvisited[node]--;
//			if(timesvisited[node]==0)
//				nodesvisited--;
//			return;
//		}
//		for(int i=0;i<paths.length&&distance<=paths.length*2;i++)
//		{
//			if(paths[node][i]&&!pathstraveled[officer][node][i])
//			{
//				pathstraveled[officer][node][i]=true;
//				traverse(i,officer,distance+1,Math.max(maxdistance, distance+1));
//				pathstraveled[officer][node][i]=false;
//			}
//		}
//		if(officer+1<pathstraveled.length)
//		{//System.out.println("NextOfficer: "+officer+1);
//			traverse(0, officer+1, 0, maxdistance);
//		}
//		timesvisited[node]--;
//		if(timesvisited[node]==0)
//			nodesvisited--;
//	}
//}