描述

作为一家初创航空公司的总裁，您启动了常旅客计划，根据客户旅行的英里数进行奖励。作为盈利性企业，您有动机最小化单次行程可获得的常旅客里程数。为了估算客户在现有航线网络中可能获得的里程数，您决定编写一个程序。

假设条件：

• 乘客行程为单程（无返程航班）
• 所有行程都选择出发城市到目的城市的最短路线
• 常旅客里程按"直线飞行距离"计算（即连接路径上各城市的地球表面最短路径）
• 地球表面视为完美球体，半径为 &4000& 英里

输入格式： 第&1& 行包含整数 &n& 表示数据集数量。每个数据集包含以下&3&部分：

1. 标题行 - 单行格式 "&X Y&"：

   • &X& 表示城市数量（&1& < &X& < &100&）
   • &Y& 表示直飞航线数量（&1& < &Y& < &100&）

2. 城市列表 - 每行格式为： "&C LA NS LO EW&"

   • &C&：城市名称（无空格，首字母大写，其余小写）
   • &LA&：纬度度数（&0& ≤ &LA& ≤ &90&）
   • &NS&：纬度方向（'N'表示北纬/'S'表示南纬）
   • &LO&：经度度数（&0& ≤ &LO& ≤ &180&）
   • &EW&：经度方向（'E'表示东经/'W'表示西经）

3. 航班列表 - 每行格式为 "&B C&"：

   • 表示城市 &B& 和 &C& 之间有直飞航班（双向等效）

特殊说明：

• 某些经度值存在多种表示方式（如 &180E& = &180W&）
• 所有经纬度均为整数
• 保证航线网络连通（任意两城市间至少存在一条路径）

输出格式： 对每个数据集，输出相距最远的两个城市（即所有城市对中最短路径最长的组合）。保证结果唯一，按字典序排列城市名称，格式为：
&城市A 城市B&

示例输入：

2
6 5
Northpole 90 N 87 E
Southpole 90 S 180 W
Equatorone 0 N 45 W
Equatortwo 0 S 90 E
Equatorthree 0 S 180 E
Equatorfour 0 N 46 W
Equatorone Equatortwo
Equatortwo Equatorthree
Equatorthree Equatorfour
Northpole Equatortwo
Southpole Equatorthree
2 1
Northpole 90 N 0 E
Southpole 90 S 0 W
Southpole Northpole

示例输出：

Equatorfour Equatorthree
Northpole Southpole