Швидкий пошук#1816
Поліцейський підрозділ стикається з ситуаціями, коли потрібно якнайшвидше обшукати декілька місць невеликою групою офіцерів. На рисунках 1 і 2 наведені схеми двох таких ситуацій. Місця, які потрібно обшукати, позначені великими літерами. Місце, позначене літерою , є спільною відправною точкою. Деякі з цих місць з'єднані шляхами. Кожен з'єднувальний шлях проходиться за одну одиницю часу; візуальний огляд окремих місць додаткового часу не потребує.
Розглянемо рисунок 1. Якщо є або більше офіцерів, обшук триває лише одну одиницю часу. Різні офіцери прямують шляхами AB, AC і AD. Якщо офіцерів двоє, повний обшук триває дві одиниці часу. Наприклад, один офіцер може пройти шляхом ABC, а інший — AD.
Розглянемо рисунок 2. Якщо б було офіцери, вони могли б рухатися шляхами ABC, ABD і AEAF, витративши одиниці часу. Якщо офіцерів двоє, вони могли б пройти шляхами ABCBD і AEAF, витративши одиниці часу.
Це досить прості приклади, які можна вирішити вручну. Для складніших ситуацій потрібна ваша програмна допомога.
Вхід складається з до наборів даних, після яких йде рядок, що містить лише число .
Кожен набір даних — це один рядок, що починається з трьох розділених пробілами додатних чисел , де — кількість місць для обшуку, — кількість офіцерів, а — кількість з'єднувальних шляхів. Обмеження: 2 \leq s \leq 10, 1 \leq n \leq 4, та p \leq 20. Далі у рядку наведено пар великих літер, розділених пробілами, які позначають шляхи між місцями. Місця позначені першими літерами латиниці. Кожне місце буде сполучене з іншими послідовністю з'єднувальних шляхів. Літери в кожній парі розташовані у зростаючому алфавітному порядку. Жодна пара літер не повторюється.
Для кожного набору даних виведіть одним рядком мінімальний час обшуку для офіцерів, які стартують з місця .
Будьте обережні з вибором алгоритму — інакше ваша програма може працювати надто довго.
Наведені у зразку набори даних відповідають описаним сценаріям.
Приклад 1