Быстрый поиск
Полицейское подразделение сталкивается с ситуациями, когда необходимо как можно быстрее обыскать несколько мест с небольшой группой офицеров. Рисунки 1 и 2 представляют диаграммы для двух таких ситуаций. Места для поиска обозначены заглавными буквами. Место, обозначенное буквой A, является общей отправной точкой. Некоторые из этих мест соединены путями. Предположим, что каждый соединительный путь занимает одну единицу времени для прохождения, а на визуальный осмотр отдельных мест времени не требуется.
Рассмотрим рисунок 1. Если есть 3 или более офицеров, поиск займет только одну единицу времени. Разные офицеры следуют путями AB, AC и AD. Если офицеров двое, полный поиск займет две единицы времени. Например, один офицер может следовать по пути ABC, а другой по пути AD.
Рассмотрим рисунок 2. Если бы было 3 офицера, они могли бы следовать путями ABC, ABD и AEAF и затратить 3 единицы времени. С 2 офицерами они могли бы следовать путями ABCBD и AEAF, и затратить 4 единицы времени.
Эти примеры достаточно просты, чтобы разобраться вручную. Для более сложных вариантов они хотят вашей помощи в программировании.
Входные данные
Входные данные будут состоять из 1 до 25 наборов данных, за которыми следует строка, содержащая только 0.
Набор данных — это одна строка, начинающаяся с положительных целых чисел, разделенных пробелами: s n p, где s — количество мест для поиска, n — количество офицеров, а p — количество соединительных путей между местами поиска. Ограничения: 2 ≤ s ≤ 10, 1 ≤ n ≤ 4, и p ≤ 20. Остальная часть строки содержит p пар заглавных букв, указывающих пути между местами, каждая пара предшествуется пробелом. Места обозначены первыми s заглавными буквами. Все места будут соединены какой-либо последовательностью соединительных путей. Две буквы в каждой паре будут в порядке возрастания алфавита. Ни одна пара букв не будет повторяться.
Выходные данные
Для каждого набора данных выводится одна строка, содержащая только минимальное время поиска для n офицеров, начинающих с места A.
Будьте осторожны с вашим алгоритмом, иначе ваше решение может занять слишком много времени.
Пример входных данных соответствует обсуждаемым сценариям.