The Leprechaun Hunt

In Irish folklore a leprechaun hides all of his treasure in a pot of gold at the end of a rainbow. Whoever catches the leprechaun gets the pot. This problem asks how hard the catching is.

A hunt with $V$ villagers and one leprechaun is a game on a simple undirected graph with $N$ nodes, where $N \ge 1 + V$. The villagers first take $V$ distinct nodes. The leprechaun then picks one of the remaining nodes as his starting position. Both sides know the graph and see every position at every moment.

Each turn works like this. Exactly one villager moves from the node he stands on to an adjacent node that no other villager occupies. A villager cannot stay put, and no turn passes without such a move. If the villager steps onto the node holding the leprechaun, the villagers win. Otherwise the leprechaun either stays where he is or moves to an adjacent node that no villager occupies.

The villagers choose their starting nodes and their moves to make the capture happen as early as possible. The leprechaun chooses his starting node and his moves to avoid capture forever, and when that is impossible, to hold out for as many turns as he can. Given a graph and the number of villagers, report how many turns the villagers need against the cleverest leprechaun.

Two graphs show what the number of villagers changes. On the cycle A B C D E F G, one villager never wins, because the leprechaun keeps walking away around the cycle. Two villagers win after 2 turns: they start at A and D, a clever leprechaun starts at F, the villager at A moves to G, and whether the leprechaun then stays at F or moves to E, a villager steps onto him on the next turn.

The second graph is the 4 cycle B, D, E, C together with a node A joined to B and to C. One villager never wins here either. The leprechaun keeps to the square, holds the corner opposite the villager whenever the villager is on the square, and stands still while the villager sits at A. Two villagers who start at B and E win on their first turn.

The input holds one or more test cases. A test case starts with a line of three integers $V$, $N$, $E$. Here $V$ is the number of villagers with $1 \le V \le 7$, $N$ is the number of nodes with $1 + V \le N \le 15$, and $E$ is the number of edges with $1 \le E \le 45$. The lines after it list the $E$ edges, at most 15 edges per line. The nodes are the first $N$ uppercase letters A, B, C and so on, and an edge is written as two letters, so AC is the edge between A and C. The $E$ edges are distinct, every edge joins two different nodes, and no node touches more than 6 edges. A line holding the single value 0 ends the input.

For each test case print one line in the form CASE k: x. Here k is the position of the test case in the input, counting from 1, and x is the smallest number of turns that guarantees the capture. When the villagers cannot capture the leprechaun, print NEVER in place of the number.