More Fun in Bicol#6246
Bicol region (Region 5) consists of six provinces: Albay, Camarines Norte, Camarines Sur, Sorsogon, and the island provinces of Catanduanes and Masbate. The region contains the following cities: Iriga City, Legazpi City, Ligao City, Masbate City, Naga City, Sorsogon City, and Tabaco City.
Figure 1: Map of Bicol Region (Locations are for illustration purposes only)
After the competition, many contestants were eager to explore the region. They started asking for the locations of certain places, and began recording relative positions between places.
The input contains several test cases.
Each test case consists of two data sets: - The first contains information about the relative position of one place with respect to another. - The second is a list of queries, each asking for the relative position of one place to another.
At the beginning of each test case, there are two integers, and : the number of entries in data set 1 and data set 2, respectively, where 1 \leq m \leq 100 and 1 \leq n \leq 50.
Each of the next lines contains information about the relative position of one city with respect to another, in the format:
city_name_1, city_name_2, relative_position
Each of the next lines is a query:
city_name_1, city_name_2
Relative positions are one of: north, south, east, west, northeast, northwest, southeast, southwest. The data is comma-delimited and names may be in mixed case. It is assumed each basic direction has a unit length: i.e., "north" is north, "northeast" is north and east, etc. The data set will not include redundant (reverse) relations.
There is a blank line between test cases. The input ends with a single integer after the final test case.
For each test case, output the relative position for each query. If the information is insufficient, output "Relative location cannot be determined". Use all information present to answer the queries.
Example 1