Problem B
Guilds

The queen is becoming concerned at the increasing complexity of guilds in her land. In particular, many small guilds are part of larger guilds which are part of still larger guilds. These chains of membership have gotten in the way of her subjects’ duties, so she has decided to keep track of where each chain ends. Henceforth, all guilds must report their top-level guild: the guild that they are part of which is not itself part of a larger guild.

For example, if the Healing Guild is part of the Potions Guild which is part of the Magic Guild which in turn is part of the Royal Guild, then after the queen’s decree the Healing, Potions, and Magic Guilds will all report their top-level guild as the Royal Guild.

Given a list of which guilds are part of which other guilds, can you help the queen determine each guild’s top-level guild?

Input

Input begins with a line containing a single integer $1 \leq n \leq 10^5$. The next $n$ lines each consist of two distinct space-separated guild names of up to $10$ lowercase English letters, indicating that the first (smaller) guild belongs to the second (larger) guild.

Every guild will appear at most once on the left-hand side of the $n$ lines, and no chain of membership forms a cycle since the second guild strictly contains the first guild in each line.

Output

For each line in the input, output a line in the same format but with the second guild replaced by the unique guild that the first guild is part of and which is not part of any larger guild.

3
healing potions
potions magic
magic royal

healing royal
potions royal
magic royal

4
smithing crafting
artisan crafting
summoning defence
conjuring summoning

smithing crafting
artisan crafting
summoning defence
conjuring defence