Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
towns
Умеете играть в города? Суть игры - в выстраивании цепочки из названий городов, в который следующее начинается на последнюю букву предыдущего и одно название используется не более одного раза.
Игру программировать не будем. Задача будет другая: из заданного набора названий городов выстроить самую короткую цепочку от одного города к другому. Саму цепочку выводить не нужно, достаточно вывести её длину.
Входные данные. В первой строке натуральное число N,
количество городов (будем считать, что их не больше 50).
В следующей строке N названий городов (все названия однословные,
записаны прописными буквами латиницы). В последней строке номера
начального и конечного города (два различных натуральных числа,
не превышающих N)
Выходные данные. Натуральное число - минимальная длина цепочки от начального города да конечного, включая начальный и конечный. Если такая цепочка невозможна, программа должна вывести -1.
Пример. При вводе следующих данных:
7
KURSK VITEBSK KIROV TOMSK ZLATOUST MOSKVA VLADIVOSTOK
5 2
программа должна вывести 4 (такую длину имеет, например, цепочка ZLATOUST-TOMSK-KIROV-VITEBSK) А вот если заменить KIROV на KIROVSK, программа выведет -1.
Для отправки решений необходимо выполнить вход.
|