Задача G: Быстрый обыск

Рисунок 1	Рисунок 2

Полиции часто требуется обыскать несколько разных местоположений небольшой группой офицеров за минимально возможное время. На рисунках 1 и 2 представлены две ситуации. Местоположения, которые надо обыскать, отмечены заглавными буквами. Местоположение, помеченное буквой A, является общей отправной точкой. Между некоторыми местоположениями есть соединяющие пути. Для прохождения каждого такого пути требуется одна единица времени, а временем обыска местоположений можно пренебречь.

Рассмотрим рисунок 1. Если на обыск пойдут 3 или более офицера полиции, то обыск займет одну единицу времени. Офицеры пойдут по путям AB, AC и AD. Если на обыск пойдет только 2 офицера, то обыск займет 2 единицы времени (например, один офицер пойдет по пути АВС, а другой AD).

Рассмотрим рисунок 2. Если на обыск отправятся 3 офицера полиции, то они могут пойти по путям ABC, ABD и AEAF, что заняло бы у них 3 единицы времени. Если на обыск офицеры отправятся вдвоем, то они могут пройти по путям ABCBD и AEAF, что займет у них 4 единицы времени.

Рассмотренные примеры слишком просты и могут быть подсчитаны вручную. Для более сложных ситуаций требуется ваша помощь.

Входные данные

Каждый тест состоит из одной строки, которая начинается с целых чисел s, n, p, разделенных пробелом. s - количество местоположений для обыска, n – количество офицеров, p – количество путей между местоположениями (2 ≤ s ≤ 10, 1 ≤ n ≤ 4, p ≤ 20). Остальная часть строки содержит p пар заглавных латинских букв, которые указывают на то, что между соответствующими местоположениями есть путь. Пары разделены между собой пробелом. Местоположения обозначаются первыми s заглавными латинскими буквами. Из каждого местоположения можно дойти до любого другого по путям. 2 буквы в каждой паре находятся в алфавитном порядке. Пары не повторяются.

Выходные данные

Позаботьтесь об эффективности вашего решения, иначе оно может не пройти по времени.

Пример входных данных соответствует описанным в условии задачи ситуациям.