Швидкий пошук
Поліцейський підрозділ стикається з ситуаціями, коли потрібно швидко обшукати кілька місць за допомогою невеликої групи офіцерів. На рисунках 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.
Будьте обережні з вашим алгоритмом, інакше ваше рішення може зайняти занадто багато часу.
Зразок вхідних даних відповідає обговорюваним сценаріям.