ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Fractal Labyrinth

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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.

Output

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

Samples

inputoutput
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
Problem Source: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.
To submit the solution for this problem go to the Problem set: 1623. Fractal Labyrinth