레프러콘 사냥

아일랜드 전설에서 레프러콘은 무지개가 끝나는 곳에 금이 든 항아리를 숨겨 두고 보물을 모두 그 안에 넣어 둔다. 레프러콘을 잡은 사람은 그 항아리를 받는다. 이 문제에서는 레프러콘을 잡기가 얼마나 어려운지 따져 본다.

마을 사람 $V$명이 레프러콘 한 명을 쫓는 사냥은 정점이 $N$개인 단순 무향 그래프 위의 게임이다. 항상 $N \ge 1 + V$이다. 먼저 마을 사람이 서로 다른 정점 $V$개를 골라 자리를 잡는다. 그다음 레프러콘이 남은 정점 중 하나를 시작 위치로 고른다. 양쪽 모두 그래프와 모든 위치를 언제나 알고 있다.

한 턴은 다음과 같이 진행한다. 마을 사람 중 정확히 한 명이 자기가 선 정점에서 다른 마을 사람이 없는 인접 정점으로 이동한다. 마을 사람은 제자리에 머무를 수 없고, 이동이 일어나지 않는 턴도 없다. 이동한 정점에 레프러콘이 있으면 마을 사람이 이긴다. 그렇지 않으면 레프러콘은 제자리에 머무르거나, 마을 사람이 없는 인접 정점으로 이동한다.

마을 사람은 최대한 빨리 잡도록 시작 위치와 이동을 고르고, 레프러콘은 영원히 잡히지 않도록, 그것이 불가능하면 최대한 여러 턴을 버티도록 시작 위치와 이동을 고른다. 그래프와 마을 사람 수가 주어질 때, 가장 영리한 레프러콘을 상대로 마을 사람이 잡는 데 필요한 턴 수를 구하라.

마을 사람 수가 무엇을 바꾸는지 그래프 두 개로 볼 수 있다. 정점 A B C D E F G가 이루는 길이 7짜리 사이클에서는 마을 사람이 한 명이면 절대 잡지 못한다. 레프러콘이 사이클을 따라 계속 달아나면 되기 때문이다. 두 명이면 2턴 만에 잡는다. 두 사람이 A와 D에서 시작하면 영리한 레프러콘은 F에서 시작하는데, A에 있던 사람이 G로 가면 레프러콘이 F에 머무르든 E로 가든 다음 턴에 잡힌다.

두 번째 그래프는 B, D, E, C가 이루는 길이 4짜리 사이클에 정점 A를 B와 C에 이어 붙인 것이다. 여기서도 마을 사람이 한 명이면 잡지 못한다. 레프러콘은 사각형 안에만 머무르면서 마을 사람이 사각형 위에 있으면 그 반대쪽 정점을 지키고, 마을 사람이 A로 가면 가만히 있으면 된다. 반면 두 명이 B와 E에서 시작하면 첫 턴에 잡는다.

입력은 테스트 케이스 하나 이상으로 이루어진다. 각 테스트 케이스는 정수 세 개 $V$, $N$, $E$가 적힌 줄로 시작한다. $V$는 마을 사람 수로 $1 \le V \le 7$이고, $N$은 정점 수로 $1 + V \le N \le 15$이며, $E$는 간선 수로 $1 \le E \le 45$이다. 그 뒤의 줄에는 간선 $E$개가 한 줄에 최대 15개씩 적혀 있다. 정점은 알파벳 대문자 앞에서부터 $N$개, 즉 A, B, C 순서로 나타내고, 간선은 두 글자로 적는다. AC는 A와 C를 잇는 간선이다. 간선 $E$개는 모두 다르고, 각 간선은 서로 다른 두 정점을 이으며, 한 정점에 붙는 간선은 6개를 넘지 않는다. 0 하나만 있는 줄이 나오면 입력이 끝난다.

각 테스트 케이스마다 CASE k: x 형식으로 한 줄씩 출력한다. k는 그 테스트 케이스가 입력에서 몇 번째인지를 1부터 센 값이고, x는 잡는 것을 보장하는 최소 턴 수이다. 마을 사람이 레프러콘을 잡을 수 없으면 수 대신 NEVER를 출력한다.