직선 거리 (As the Crow Flies)

당신은 신생 항공사의 대표이며, 고객이 이동한 마일마다 보상을 주는 상용 고객 우대 프로그램을 시작했습니다. 영리 기업이므로, 한 번의 여정에서 승객이 적립할 수 있는 마일을 최소화하고 싶습니다. 현재 노선망에서 고객이 최대로 적립할 수 있는 마일이 얼마인지 가늠하기 위해 프로그램을 작성하기로 했습니다.

가정:

• 승객의 여정은 편도입니다(귀국편 없음).
• 모든 여정은 출발 도시에서 도착 도시까지의 최단 경로를 따릅니다.
• 적립 마일은 "직선 거리(as the crow flies)", 즉 경로상의 도시들을 잇는 지구 표면 위 최단 경로의 길이로 계산합니다.
• 지구 표면은 반지름 4000마일의 완전한 구입니다.

첫 번째 줄에는 데이터 집합의 개수를 나타내는 정수 $n$이 주어집니다. 각 데이터 집합의 형식은 다음과 같습니다.

하나의 데이터 집합은 세 부분으로 이루어집니다.

1. 헤더 줄 — X Y 형식의 한 줄로, $X$는 도시의 수, $Y$는 노선망의 직항 구간(flight leg) 수입니다. 둘 다 100보다 작은 양의 정수입니다.

2. 도시 목록 — 한 줄에 한 도시씩, C LA NS LO EW 형식으로 주어집니다.

   • C: 도시 이름(공백 없음, 알파벳, 첫 글자만 대문자).
   • LA: 위도(0부터 90까지).
   • NS: 위도의 방향(N은 적도 북쪽, S는 적도 남쪽).
   • LO: 경도(0부터 180까지).
   • EW: 경도의 방향(E는 본초 자오선 동쪽, W는 서쪽).

3. 노선 목록 — 한 줄에 한 쌍씩, B C 형식으로 직항으로 연결된 두 도시를 나타냅니다. B C와 C B는 같습니다.

참고:

• 일부 경도는 여러 방식으로 표기될 수 있습니다(예: 180E = 180W).
• 입력의 모든 위도·경도 값은 정수입니다.
• 노선망은 연결되어 있습니다(임의의 두 도시 사이에 적어도 하나의 경로가 존재합니다).

각 데이터 집합에 대해, 서로 가장 먼 두 도시를 출력합니다. 여기서 "가장 멀다"는 것은 두 도시 사이 최단 경로의 길이가 모든 도시 쌍 중 가장 긴 경우를 뜻합니다. 동점은 없음이 보장됩니다. 두 도시 이름을 사전순으로 정렬하여 한 줄에, 사이에 공백 하나를 두고 출력하세요.