ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1623. Fractal Labyrinth

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Roman adores all kinds of labyrinths. He solves them since his early childhood. Yesterday he found a new, extremely amazing sort of labyrinth. He called it a "fractal labyrinth".
Imagine a house with N doors. Inside it, there are K houses, each of them an entire copy of the "outer" one. Some doors are connected by roads. If you draw these roads, you get something like this:
Problem illustration
Remembering that each "inner" house is a copy of the "outer house", you get the following picture as a result:
Problem illustration
The following picture is an example of a house with 2 inner houses:
Problem illustration
For outer house, some door is defined as "input" and some door as "output", so we finally come up to a labyrinth. Assuming that length of each road is 1, find the length of the shortest path in such labyrinth.

Исходные данные

In the first line there are numbers N (2 ≤ N ≤ 20) and K (0 ≤ K ≤ 5). The next line contains M, the number of the roads. In the following M lines there are descriptions of the roads, one per line.
Each road description is formatted in the following way:
<house-number>.<door-number> - <house-number>.<door-number>
where left and right part of description specify the connected doors (a door is described by its number and number of house it belongs to). Each road is bidirectional. The "outer" house has number 0, "inner" houses have numbers from 1 to K. Door numbers start with 0. No two roads connect the same pair of doors. No road connects a door to itself.
In the last line there are numbers of input and output door Di and Do. These numbers may coincide.

Результат

If there exists a path from input to output, print the minimal length of such path. Otherwise, print "no solution".

Примеры

исходные данныерезультат
12 1
11
0.0 - 1.1
0.1 - 0.2
1.2 - 1.3
0.3 - 0.4
1.4 - 1.5
0.5 - 0.6
1.6 - 1.7
0.7 - 0.8
1.8 - 1.9
0.9 - 0.10
1.10 - 0.11
0 11
11
8 0
8
0.0 - 0.2
0.1 - 0.3
0.2 - 0.4
0.3 - 0.5
0.4 - 0.6
0.5 - 0.7
0.6 - 0.0
0.7 - 0.1
2 5
no solution
Источник задачи: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.