Problem B - Prester John

Background

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.

Problem

Given two maps, compute the minimum length of a common path to the Prester location.

Input

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.

Output

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.


Sample Input

2

1

2

0 tunnel 1

1 bridge 1

3

2

3

0 tunnel 1

1 bridge 2

2 river 2

 

Sample Output

2