// Arup Guha
// 2/7/2015
// Solution to 2014 MCPC Problem D: Leprechaun Hunt

import java.util.*;

public class d {

	final public static int UNFILLED = 1000000000;
	public static int[][] dp;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int people = stdin.nextInt();
		int loop = 1;

		// Read through cases.
		while (people != 0) {

			// Set up graph.
			int v = stdin.nextInt();
			int e = stdin.nextInt();
			boolean[][] graph = new boolean[v][v];

			// Add edges.
			for (int i=0; i<e; i++) {
				String edge = stdin.next();
				graph[edge.charAt(0)-'A'][edge.charAt(1)-'A'] = true;
				graph[edge.charAt(1)-'A'][edge.charAt(0)-'A'] = true;
			}

			// Will store answers.
			dp = new int[1 << v][v];
			for (int i=0; i<(1<<v); i++)
				Arrays.fill(dp[i], UNFILLED);

			// Fill in slots where answer is 0 or 1. (Lep and Villager share a vertex.)
			for (int i=0; i<(1<<v); i++) {
				for (int j=0; j<v; j++) {
					if ((i & (1<<j)) > 0)
						dp[i][j] = 0;
					else {
						for (int k=0; k<v; k++)
							if ((i & (1 << k)) > 0 && graph[k][j])
								dp[i][j] = 1;
					}
				}
			}

			// Output result.
			System.out.print("CASE "+loop+": ");
			int result = solve(graph, people);
			if (result < UNFILLED) System.out.println(result);
			else                System.out.println("NEVER");

			// Go to next case.
			loop++;
			people = stdin.nextInt();
		}
	}

	public static int solve(boolean[][] graph, int people) {

		// Set these up.
		int v = graph.length;
		int finalAns = UNFILLED;

		// Main loop.
		while (true) {

			boolean update = false;

			// Try each possible location of villagers.
			for (int mask = 0; mask < (1 << v); mask++) {

				// Need the right number of people.
				if (Integer.bitCount(mask) != people) continue;

				for (int lep=0; lep<v; lep++) {

					if (dp[mask][lep] != UNFILLED) continue;

					// See if this state can be solved based on previous solved states.
					dp[mask][lep] = update(graph, mask, lep);
					if (dp[mask][lep] < UNFILLED) update = true;
				}

			}

			// We can stop when no new game states are added in an iteration.
			if (!update) break;
		}

		int myScore = UNFILLED;

		// Go through all masks with people bits on.
		for (int i=0; i<(1<<v); i++) {

			if (Integer.bitCount(i) != people) continue;
			boolean winner = true;
			int res = 0;

			// Go through all places leprechaun could have started.
			for (int j=0; j<v; j++) {
				if (dp[i][j] == UNFILLED) {
					winner = false;
					res = UNFILLED;
					break;
				}

				// Leprechaun is trying to maximize the score.
				res = Math.max(res, dp[i][j]);
			}

			// Villagers are trying to minimize it.
			myScore = Math.min(myScore, res);
		}
		return myScore;
	}

	public static int update(boolean[][] graph, int mask, int lep) {

		int v = graph.length;

		// Find all new distinct subsets we(villagers) could visit.
		HashSet<Integer> newMasks = new HashSet<Integer>();
		for (int i=0; i<v; i++) {

			// We have someone at node i.
			if ((mask & (1 << i)) > 0) {

				// Try moving them to all adjacent nodes that don't have someone.
				for (int j=0; j<v; j++) {
					if (!graph[i][j]) continue;
					if ((mask & (1 << j)) == 0)
						newMasks.add(mask - (1 << i) + (1 << j));
				}
			}
		}

		int bestScore = UNFILLED;

		// Go through each potential next mask.
		for (Integer nextMask: newMasks) {

			// Leprechaun can just stay...
			if (dp[nextMask][lep] == UNFILLED) continue;

			// This is our starting score, if he stays.
			int score = dp[nextMask][lep] + 1;
			boolean canDo = true;

			// Try seeing if every move forces him into a known "winning" position for us.
			for (int i=0; i<v; i++) {
				if (!graph[i][lep]) continue;

				// Oops, he can escape.
				if (dp[nextMask][i] == UNFILLED) {
					canDo = false;
					break;
				}

				// Update our score.
				score = Math.max(score, 1+dp[nextMask][i]);
			}

			// This is our result.
			if (canDo) bestScore = Math.min(bestScore, score);
		}

		return bestScore;
	}
}