빠른 수색

한 경찰 부대는 적은 인원으로 여러 장소를 최대한 빠르게 수색해야 하는 상황을 자주 겪는다. 그림 1과 그림 2는 그러한 두 가지 상황을 나타낸다. 수색할 장소에는 대문자가 붙어 있으며, A로 표시된 장소가 공통 출발점이다. 일부 장소 쌍은 연결로로 이어져 있다.

연결로 하나를 지나는 데에는 시간 1이 걸리고, 장소 자체를 수색하는 데에는 시간이 걸리지 않는다. 모든 경찰관은 같은 순간에 A에서 출발하여 동시에 움직이므로, 전체 수색 시간은 가장 늦게 끝나는 경찰관이 마치는 순간이다. 모든 장소는 적어도 한 명의 경찰관이 방문해야 하며, 목표는 전체 수색 시간을 최대한 작게 만드는 것이다.

그림 1을 보자. 경찰관이 3명 이상이면 수색은 시간 1 만에 끝난다. 각 경찰관이 서로 다른 경로 AB, AC, AD를 따라가면 된다. 경찰관이 2명이면 수색에는 시간 2가 걸린다. 예를 들어 한 명은 경로 ABC를, 다른 한 명은 AD를 따라간다.

그림 2를 보자. 경찰관이 3명이면 경로 ABC, ABD, AEAF를 따라가 시간 3 만에 끝낼 수 있다. 경찰관이 2명이면 ABCBD와 AEAF를 따라가 시간 4 만에 끝낼 수 있다.

이렇게 작은 경우는 손으로 쉽게 풀 수 있다. 더 복잡한 배치에 대해서는 여러분의 프로그래밍 도움이 필요하다.

입력은 1개에서 25개의 데이터 집합으로 이루어지며, 마지막에는 0 하나만 있는 줄이 온다.

각 데이터 집합은 한 줄이며, 공백으로 구분된 세 양의 정수 s n p로 시작한다. 여기서 s는 수색할 장소의 수, n은 경찰관의 수, p는 장소를 잇는 연결로의 수이다. 제한은 $2 \le s \le 10$, $1 \le n \le 4$, $p \le 20$이다. 줄의 나머지 부분에는 연결로를 나타내는 문자 쌍 p개가 각각 앞에 공백을 두고 이어진다. 장소는 앞에서부터 s개의 대문자로 표시되며, 모든 장소는 A에서 어떤 연결로들을 거쳐 도달할 수 있다. 각 쌍의 두 문자는 알파벳 오름차순으로 적히고, 같은 쌍은 두 번 나오지 않는다.

각 데이터 집합마다, 모두 A에서 출발하여 모든 장소를 함께 방문하는 경찰관 n명의 최소 전체 수색 시간을 한 줄에 출력한다.

알고리즘을 신중하게 설계하지 않으면 실행이 너무 느려질 수 있다.