cho.sh

As the Crow Flies

Time limit1sMemory limit128 MB

Problem

As the president of a startup airline, you have launched a frequent flier program that rewards customers for every mile they travel. Because you run a for-profit company, you want to minimize the number of frequent flier miles a passenger can earn on any single trip. To estimate how many miles a customer could accumulate on your existing network, you decide to write a program.

Assumptions:

  • A passenger's itinerary is one-way (there is no return flight).
  • Every itinerary follows the shortest route from the departure city to the destination city.
  • Frequent flier miles are measured "as the crow flies," that is, along the shortest path over the earth's surface connecting the cities on the route.
  • The earth's surface is a perfect sphere with a radius of 4000 miles.

Input

The first line contains a single integer $n$, the number of data sets. Each data set is formatted as follows.

A data set has three parts:

  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 network. Both are positive integers less than 100.

  2. City list — one city per line, in the format C LA NS LO EW, where:

    • C is the city name (no spaces, alphabetic, only the first letter uppercase).
    • LA is the latitude in degrees (0 to 90).
    • NS is the latitude hemisphere (N for north or S for south of the equator).
    • LO is the longitude in degrees (0 to 180).
    • EW is the longitude hemisphere (E for east or W for west of the prime meridian).

  3. Flight list — one city pair per line, in the format B C, meaning cities B and C are directly connected by a flight leg. B C is equivalent to C B.

Notes:

  • Some longitudes can be written in more than one way (for example, 180E = 180W).
  • All latitude and longitude degrees in the input are integers.
  • The network is connected (there is at least one route between any two cities).

Output

For each data set, output the two cities that are farthest apart, where "farthest" means the pair whose shortest route between them is the longest over all city pairs. There are guaranteed to be no ties. Print the two city names on one line, separated by a single space, sorted in dictionary order.