693. Travel sequencing

Mary needs to fly from one place to another , Because there is no direct flight , So we need to transfer many flights halfway .

for example ：SFO -> DFW DFW -> JFK JFK -> MIA MIA -> ORD.

Obviously, it is impossible to travel to the same transit city twice or more , Because it doesn't make sense .

Unfortunately , She messed up the order of her tickets , It is not easy for her to arrange the tickets according to the order of travel .

Please help Mary arrange her ticket , Arrange the tickets in the correct order .

Input format

The first line contains integers T, Expressing common ownership T Group test data .

The first row of each set of data contains an integer N.

Next 2N That's ok , Every time 2 Row group , Indicates the information of a ticket , Each line contains a string , The first line indicates the place of departure , The second line indicates the destination .

Output format

Each group of data outputs a result , Each result takes up one line .

The result is expressed as Case #x: y, among xx It's the group number （ from 1 Start ）,y Is a list of tickets representing the actual trip , Each leg of the journey should be marked with source-destination Form output , The segments are separated by spaces .

Data range

1≤T≤100,
1≤N≤10000

sample input ：

2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA

sample output ：

Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD

Code ：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    
    int T;
    cin >> T;
    for (int k = 1; k <= T; k++)
    {
    
        int n;
        cin >> n;
        unordered_map<string, string> next;
        unordered_set<string> S;

        while (n--)
        {
    
            string a, b;
            cin >> a >> b;
            next[a] = b;
            S.insert(b);
        }

        string head;
        for (auto &[a, b] : next)
            if (!S.count(a))
            {
    
                head = a;
                break;
            }

        printf("Case #%d: ", k);
        while (next.count(head)) // Yes 
        {
    
            cout << head << '-' << next[head] << ' ';
            head = next[head];
        }
        cout << endl;
    }

    return 0;
}