During a national holiday torch relay, the flame is carried from city to city in one unbroken chain: every leg of the relay hands the torch from exactly one departure city to exactly one arrival city, no city ever hands the torch off more than once, and the chain never branches or loops. Somewhere along this chain sits the final city -- the place where the torch arrives and the relay ends -- and it is guaranteed that exactly one such city exists among all the cities that appear in the legs. Given the list of relay legs, each described by its departure and arrival city, find and report that final city.
The first line contains a single integer n, the number of relay legs.
Each of the next n lines contains two space-separated tokens a b, meaning one leg carried the torch from city a to city b. The legs are not necessarily listed in the order the torch actually travelled. City names consist only of English letters, digits, and the characters ., , and _ (no spaces within a name), and are at most 20 characters long.
Print the single city name where the relay ends -- the only city among all the cities appearing in the input that never appears as a departure city.
Example 1
Input
3 London Paris Paris Berlin Berlin Rome
Expected
Rome
Explanation
The legs chain together as London -> Paris -> Berlin -> Rome. Rome receives the torch but never appears as a departure city in any leg, so Rome is the final city.
Example 2
Input
1 Delhi Mumbai
Expected
Mumbai
Explanation
With a single leg, Delhi is the only departure city and Mumbai only ever appears as an arrival city, so Mumbai is the final city.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →