The first line contains a single integer n indicating the number of data sets. Each data set will be formatted according to the following description:
A single data set has 3 components:
1. Header Line - A single line, "X Y", where X is the number of cities and Y is the number of flight legs in the airline's network. Both will be positive integers less than 100.
2. City List - A list of cities and their locations, one city per line. The line will be of the format
"C LA NS LO EW" where:
- C is the name of the city (no spaces, alphabetical, first letter only upper case)
- LA is the degrees of latitude where the city is located (from 0 to 90)
- NS is the direction of latitude ('N'orth or 'S'outh of the equator)
- LO is the degrees of longitude where the city is located (from 0 to 180)
- EW is the direction of longitude ('E'ast or 'W'est of the prime meridian)
3. Flight List - A list of city pairs of the format "B C" representing different cities that are directly connected by flight legs, one pair per line. Note that "B C" is equivalent to "C B".
- Some longitude measurements can be represented in multiple ways (i.e., 180E = 180W)
- All degrees of latitude and longitude given in the input will be integers.
- The airline's network is connected (i.e., there is at least one route between any two cities).