뒤섞인 여행 일정 정렬하기

어느 날, Mary는 여러 번의 항공편 환승을 거쳐 어떤 곳에서 다른 곳으로 가는 편도 항공권을 샀다.

예: SFO->DFW DFW->JFK JFK->MIA MIA->ORD.

당연히 한 도시에서 두 번 이상 환승하는 것은 말이 되지 않는다. 따라서 Mary는 그렇게 하지 않는다.

안타깝게도 Mary는 항공권을 받은 뒤 항공권들을 뒤섞었고, 그 순서를 잊어버렸다.

Mary가 항공권들을 올바른 순서로 재배열하도록 도와주자.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 각 케이스에서 입력으로 주어지는 항공권들은 Mary가 구매한 전체 여행 일정에서 뒤섞인 것이다. 즉, 유효한 여행 일정으로 복원할 수 있음이 보장된다.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{4}$.

(예제의 두 번째 케이스에 해당하는 구간은 다음과 같이 볼 수 있다) MIA-ORD, DFW-JFK, SFO-DFW, JFK-MIA

첫 번째 줄에는 테스트 케이스의 수 T가 주어지며, 그 뒤에 T개의 케이스가 이어진다. 각 케이스는 정수 N으로 시작한다. 이어서 N개의 항공권이 주어진다. 다음 2개의 각 줄에는 항공권의 출발지와 목적지가 주어진다.

각 테스트 케이스마다 "Case #x: itinerary"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), 여행 일정은 실제 여행 일정을 나타내도록 정렬된 항공권 목록이다. 여행 일정의 각 항공편 구간은 출발지-목적지 공항 코드의 쌍으로 출력해야 한다.