뒤섞인 항공권 정렬하기 (Large)

메리는 여러 번 환승하는 편도 항공권 묶음을 샀다. 예를 들어 SFO에서 DFW, DFW에서 JFK, JFK에서 MIA, MIA에서 ORD로 이어지는 식이다.

같은 도시를 두 번 이상 거치는 일정은 의미가 없으므로 메리는 그런 일정을 사지 않는다.

그런데 항공권을 받은 뒤 순서를 섞어 버렸고, 원래 순서를 잊었다. 섞인 항공권을 실제 여정 순서대로 정렬하는 프로그램을 작성하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 항공권의 수 $N$이 주어진다. 그 뒤에 항공권 $N$장이 주어지며, 항공권 한 장은 두 줄을 차지한다. 첫 줄에 출발지, 둘째 줄에 도착지가 있다. 공항 코드는 알파벳 대문자 세 글자다.

각 테스트 케이스마다 Case #x: itinerary 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, itinerary는 실제 여정 순서로 정렬한 항공권 목록이다. 항공권 한 장은 출발지-도착지 형태로 쓰고, 항공권 사이는 공백 하나로 구분한다.

• $1 \le T \le 100$
• $1 \le N \le 10^4$
• 입력의 항공권은 메리가 산 여정 하나를 섞은 것이다. 즉, 항상 유효한 여정 하나로 복원된다.
• 한 테스트 케이스에서 같은 도시를 두 번 방문하는 일은 없으므로 답은 유일하다.