Sort a scrambled itinerary (Large)

Mary bought a bundle of one way tickets that take her through several transfers. For example, SFO to DFW, DFW to JFK, JFK to MIA, MIA to ORD.

Transferring at the same city twice or more makes no sense, so Mary never buys such an itinerary.

After she received the tickets she shuffled them and forgot the original order. Write a program that sorts the shuffled tickets back into the real itinerary order.

The first line contains the number of test cases $T$. The $T$ test cases follow.

The first line of each test case contains the number of tickets $N$. Then $N$ tickets follow, and each ticket takes two lines: the source on the first line and the destination on the second line. An airport code is three uppercase letters.

For each test case, print one line in the form Case #x: itinerary, where $x$ is the test case number starting from 1 and itinerary is the list of tickets sorted into the real itinerary order. Write each ticket as source-destination and separate consecutive tickets with a single space.

• $1 \le T \le 100$
• $1 \le N \le 10^4$
• The tickets of a test case are a shuffle of one itinerary Mary bought, so they always rebuild into one valid itinerary.
• No city is visited twice inside a test case, so the answer is unique.