#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <vector>
using namespace std;
#define MAX_N 15
#define MAX_E 45
#define MAX_DEG 6
#define MAX_V 7
#define LOG_N 4
int DEBUG = 0;
int V; int N; int E; vector<vector<int> > adj;
typedef long long StateCode;
struct State {
bool villagerTurn;
int leprechaun;
set<int> villagers;
State() { }
const static StateCode MASK = (1L << LOG_N) - 1;
StateCode code() const {
StateCode s = villagerTurn;
s |= (leprechaun << 1);
int offset = 1+LOG_N;
for (set<int>::const_iterator it = villagers.begin();
it != villagers.end(); ++it) {
s |= ( ((StateCode) *it) << offset);
offset += LOG_N;
}
return s;
}
State(StateCode c) {
villagerTurn = (c % 2 == 1);
leprechaun = (c >> 1) & MASK;
for (int j=0; j<V; j++)
villagers.insert((c >> (1+LOG_N*(1+j))) & MASK);
if (code() != c) {
cerr << "INVALID RECONSTRUCTION" << endl;
cerr << c << endl;
cerr << code() << endl;
cerr << toString() << endl;
}
}
vector<State> neighbors() const {
vector<State> nbrs;
State copy(*this);
copy.villagerTurn = !villagerTurn;
if (villagerTurn) {
for (set<int>::const_iterator it = villagers.begin();
it != villagers.end(); ++it) {
int cur = *it; copy.villagers.erase(cur);
for (int j=0; j < adj[cur].size(); j++) {
if (copy.villagers.insert(adj[cur][j]).second) { nbrs.push_back(copy);
copy.villagers.erase(adj[cur][j]);
}
}
copy.villagers.insert(cur);
}
} else { if (leprechaun != N)
nbrs.push_back(copy); for (int j=0; j < adj[leprechaun].size(); j++) {
if (copy.villagers.count(adj[leprechaun][j]) == 0) {
copy.leprechaun = adj[leprechaun][j];
nbrs.push_back(copy);
}
}
}
return nbrs;
}
string toString() const {
string result;
result += ((char) ('A' + leprechaun));
result += ',';
for (set<int>::const_iterator it = villagers.begin();
it != villagers.end(); ++it) {
result += ((char) ('A' + *it));
}
result += " (";
result += (villagerTurn ? "villager" : "leprechaun");
result += " to move)";
return result;
}
};
void generateVillagerPlacements(vector<State>& result, State& model) {
if (model.villagers.size() == V) {
result.push_back(model);
} else {
int next = (model.villagers.empty() ? 0 : 1 + *(model.villagers.rbegin()));
for (int j=next; j < N; j++) {
model.villagers.insert(j);
generateVillagerPlacements(result, model);
model.villagers.erase(j);
}
}
}
map<StateCode,int> win;
bool trapped(const State& s, int plies) {
if (DEBUG > 2)
cerr << " testing trapped for " << s.toString() << " " << plies << endl;
vector<State> options = s.neighbors();
for (int j=0; j < options.size(); j++) {
StateCode code = options[j].code();
if (win.find(code) == win.end() || win[code] >= plies)
return false;
}
if (DEBUG > 2)
cerr << " TRAPPED is true" << endl;
return true;
}
int analyze() {
set<StateCode> fringe;
vector<State> placements;
State model;
model.villagerTurn = false;
model.leprechaun = 0;
generateVillagerPlacements(placements, model);
for (int j=0; j < placements.size(); j++) {
State& s(placements[j]);
for (set<int>::const_iterator it = s.villagers.begin();
it != s.villagers.end(); ++it) {
s.leprechaun = *it;
StateCode code = s.code();
win[code] = 0;
fringe.insert(code);
}
}
int plies = 0;
while (!fringe.empty()) {
plies++; set<StateCode> newFringe;
for (set<StateCode>::const_iterator it = fringe.begin(); it != fringe.end(); ++it) {
State s(*it);
if (DEBUG > 1)
cerr << "win = " << win[*it] << " for " << s.toString() << endl;
s.villagerTurn = !s.villagerTurn; if (s.villagerTurn) {
vector<State> nbrs = s.neighbors();
for (int j=0; j < nbrs.size(); j++) {
nbrs[j].villagerTurn = true;
StateCode code = nbrs[j].code();
if (DEBUG > 3) cerr << " Considering " << nbrs[j].toString() << endl;
if (win.find(code) == win.end()) {
if (DEBUG > 2) cerr << " Adding to fringe " << nbrs[j].toString() << endl;
win[code] = plies;
newFringe.insert(code);
}
}
} else {
State special(s);
special.leprechaun = N;
if (DEBUG > 2) cerr << " Considering special " << special.toString() << endl;
if (trapped(special, plies)) {
if (DEBUG > 0) cerr << "Winning initial state " << special.toString() << endl;
return plies-1; }
vector<State> nbrs = s.neighbors();
for (int j=0; j < nbrs.size(); j++) {
nbrs[j].villagerTurn = false;
StateCode code = nbrs[j].code();
if (DEBUG > 3) cerr << " Considering " << nbrs[j].toString() << endl;
if (win.find(code) == win.end())
if (trapped(nbrs[j], plies)) {
if (DEBUG > 2) cerr << " Adding to fringe " << nbrs[j].toString() << endl;
win[code] = plies;
newFringe.insert(code);
}
}
}
}
fringe.swap(newFringe);
}
return -1; }
int main(int argv, char** argc) {
ifstream fin((argv == 1) ? "hunt.in" : argc[1]);
if (argv > 2) DEBUG = atoi(argc[2]);
int trial=0;
while (true) {
++trial;
fin >> V;
if (V == 0) break;
fin >> N >> E;
adj.clear();
adj.resize(1+N);
for (int j=0; j < E; j++) {
string edge;
fin >> edge;
int u(edge[0]-'A'), v(edge[1]-'A');
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int u=0; u<N; u++)
adj[N].push_back(u);
win.clear();
int plies = analyze();
if (DEBUG > 0) cerr << "Solved " << win.size() << " states" << endl;
cout << "CASE " << trial << ": ";
if (plies == -1)
cout << "NEVER" << endl;
else
cout << (1+plies)/2 << endl; }
}