Where was the Kingdom of Prester John?
There are many maps showing the way to it, but unfortunately it seems hard to
establish a sensible agreement. India? Ethiopia? Mongolia? Syria? PuzzlingÉ
Well, what would one expect from the descendant of the Three Wise Men?
An idea is to follow the directions in
two maps at the same time, and if the directions lead to the same place, we can
find Prester. Well, Òinformation technologyÓ may help here. Write a program
that, given two medieval maps of the world indicating the location of the
Mythical Kingdom, finds the length of the common shortest path to the location
where the Prester was seen.
Given two maps, compute the minimum
length of a common path to the Prester location.
The input contains the description of a
pair of maps, in sequence. Each map is given by a positive integer L, not greater than 50,000, in a single line, indicating the number
of locations in the map. Next, there is an integer in the range [0, L-1] indicating the location, in a single line, where the Prester was
seen. Next, there is a positive integer P, not
greater than 100,000, in a single line, indicating the number of paths in the
description of the map. Then, the description of the map follows. Each path in
the map is listed in a separate line, and has the form
L1 description L2
where L1
and L2 are integers in the range [0, L-1] indicating a location, and description is a string with no more than 8 characters, indicating the name of
a path from location L1 to location L2. It is known that location 0
represents the same place in all maps.
An integer in a single line indicating
the length of the shortest sequence of path descriptions that is common to both
maps, and that, in both maps, lead to a location of the Prester. If there is no
common path leading to the Prester location, your program should write -1 as result.
2
1
2
0 tunnel 1
1 bridge 1
3
2
3
0 tunnel 1
1 bridge 2
2 river 2
Sample Output
2