Where was the Kingdom of Prester John? There are many maps showing the way to it, but unfortu- nately 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 minimumlength of a common path to the Prester location. Input Input consists of multiple test cases, each of them as described below. The first line of the input contains the number of test cases. There is a blank line before each dataset. 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 For each test case, write 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. Print a blank line between datasets. Sample Input 1 2 1 2 0 tunnel 1 1 bridge 1 3 2 3 0 tunnel 1
2/2 1 bridge 2 2 river 2 Sample Output 2