H :: Prester John

Time Limit: 10 Seconds Memory Limit: 32768 KB

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.

Input

A positive integer P in a single line followed by a sequence of P pairs of maps. 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 unidirectional path from location L1 to location L2. It is known that location 0 represents the same place in all maps. The descriptions of paths in each map will be distinct.

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

1
2
1
2
0 tunnel 1
1 bridge 1
3
2
3
0 tunnel 1
1 bridge 2
2 river 2

Sample Output

Submit