Задача 06A. Кот-Летун ≡

Автор:	Н. Шурло, А. Марченко		Ограничение времени:	1 сек
Входной файл:	test.sql		Ограничение памяти:	256 Мб
Выходной файл:	test.log

Условие

Кот-Летун, известный своими амбициозными планами по захвату всех сырных запасов мира, решил отправиться в путешествие по городам, где производят самые вкусные сорта сыра. У него есть карта, на которой отмечены города, соединенные дорогами. Каждый город славится своим уникальным сыром, и Кот-Летун хочет попробовать их все, но с одним условием: он должен обязательно заглянуть в город "Камамбер" (город К), где производят его любимый сыр.

Кот-Летун - кот занятой, поэтому он хочет найти все самые короткие маршруты от города "Альпийский" (город А) до города "Моцарелла" (город М), обязательно проходящие через "Камамбер". При этом он не хочет посещать один и тот же город дважды, чтобы не переедать сыра (ведь у него еще много планов на день).

Помогите Коту-Летуну найти все кратчайшие маршруты, удовлетворяющие его условиям, чтобы он смог насладиться сыром и продолжить свои приключения!

Кот-Летун предупреждает, что если вы не поможете ему с маршрутами, он может случайно съесть ваш обед. Будьте осторожны!

    CREATE TABLE Roads (
        from_city TEXT NOT NULL,
        to_city TEXT NOT NULL,
        PRIMARY KEY (from_city, to_city)
    );

Схема БД в UML-нотации:

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

Решение следует представить в виде текстового файла, содержащего единственный SQL-запрос.

Формат входного файла

Пример тестовой БД.

Формат выходного файла

Выведите список найденных маршрутов с указанием их длин как показано в примере: [["A -> B -> E -> I -> K -> M", 5], ["A -> V -> J -> I -> K -> M", 5]]

Ограничения

Предполагается, что для работы с базой данных используется SQLite3.

---