// Arup Guha
// 2/10/2013
// Solution to 2010 MCPC Regional Problem G: Quick Search

import java.util.*;

public class g {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();

		// Process each case.
		while (n != 0) {

			int numCops = stdin.nextInt();
			int numEdges = stdin.nextInt();

			// Get graph.
			ArrayList[] edgeList = new ArrayList[n];
			for (int i=0; i<n; i++)
				edgeList[i] = new ArrayList<Integer>();

			// Create an edge list for the graph.
			for (int i=0; i<numEdges; i++) {
				String s = stdin.next();
				int v1 = s.charAt(0) - 'A';
				int v2 = s.charAt(1) - 'A';
				edgeList[v1].add(v2);
				edgeList[v2].add(v1);
			}

			// Output and get next case.
			System.out.println(solve(numCops, edgeList));
			n = stdin.nextInt();
		}
	}

	// Uses a BFS through the search space to identify the smallest possible answer.
	public static int solve(int numCops, ArrayList[] edgeList) {

		// Num nodes in graph.
		int n = edgeList.length;

		LinkedList<Integer> q = new LinkedList<Integer>();
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

		// Start state: all cops at location 0, takes 0 moves.
		q.offer(mypow(10,numCops));
		map.put(mypow(10,numCops), 0);

		// Run BFS until queue is empty.
		while (q.size() > 0) {

			int state = q.poll();
			int steps = map.get(state);

			// Extract what's visited and where the cops are.
			int visited = state/(mypow(10, numCops));
			int copLoc = state%mypow(10, numCops);

			// We have a solution!
			if (visited == ((1 << n) - 1)) {
				return steps;
			}

			// Get the next place the cops could be.
			ArrayList<Integer> nextCops = getNextState(copLoc, edgeList, numCops);

			// Add all unique states to our queue.
			for (int i=0; i<nextCops.size(); i++) {

				// When we use bit masks, calculating where we've been is easy.
				int bitmask = getBitMask(nextCops.get(i), numCops);
				int newvisited = visited | bitmask;
				int newstate = newvisited*mypow(10, numCops) + nextCops.get(i);

				// Add if necessary.
				if (!map.containsKey(newstate)) {
					q.offer(newstate);
					map.put(newstate, steps+1);
				}
			}

		}

		// Should never get here.
		return 100;
	}

	// Returns a bitmask representation of the cops stored in value for numCops.
	public static int getBitMask(int value, int numCops) {

		// XOR in each spot.
		int val = 0;
		for (int i=0; i<numCops; i++) {
			int digit = value%10;
			val = val | (1 << digit);
			value = value/10;
		}
		return val;
	}

	// Returns base ^ exp.
	public static int mypow(int base, int exp) {
		int ans = 1;
		for (int i=0; i<exp; i++)
			ans = ans*base;
		return ans;
	}

	// Return all the possible next locations of the cops.
	public static ArrayList<Integer> getNextState(int copLoc, ArrayList[] edgeList, int numCops) {

		ArrayList[] next = new ArrayList[numCops];

		// Get a list of each cop's
		for (int i=0; i<numCops; i++) {
			int curCop = copLoc%10;
			next[i] = edgeList[curCop];
			copLoc = copLoc/10;
		}

		// Get this list and return.
		return getCombos(next, 0);
	}

	// Recursive function that returns all combinations by taking one value from
	// list[index], one from list[index+1], ... list[list.size()-1].
	public static ArrayList<Integer> getCombos(ArrayList[] list, int index) {

		// Base case.
		if (index == list.length-1)
			return list[list.length-1];

		// Get the rest of the numbers.
		ArrayList<Integer> temp = getCombos(list, index+1);

		ArrayList<Integer> ans = new ArrayList<Integer>();

		// Form new list by adding each number from this list to the previous lists.
		for (int i=0; i<list[index].size(); i++) {
			for (int j=0; j<temp.size(); j++) {
				Integer newVal = (Integer)temp.get(j)*10 + (Integer)list[index].get(i);
				ans.add(newVal);
			}
		}

		return ans;
	}
}