Baba is Rabbit

Time limit1sMemory limit512 MB

Summary

Given commands of the form p is q, find all objects reachable from Baba by applying one or more commands, printed in lexicographic order.

Level: Medium4 of 10
Topics: Graph, DFS, Hash map, Sorting
Solved: No attempts yet

Problem

Won is playing a game that is popular these days. This game uses the word is to turn one object into another. The rules are as follows.

At the start of the game, several commands are set up.
- Every command has the form p is q, where p and q are objects.
For two objects p and q, the command p is q turns object p into object q.
- This action is called applying the command.

If there are two or more commands that can be applied to some object p, you can pick any one of them and apply it. (You may also apply no command at all.) And applying commands one or more times to any object p never results in p again.

Given the commands set up at the start of the game, find out which objects Baba can be turned into by applying commands.

Input

The first line gives the total number of commands N (1 ≤ N ≤ 100,000).

The next N lines give the commands. Each command is given in the form p is q, where p and q are strings of length at most 10 whose first character is an uppercase English letter and whose remaining characters are lowercase English letters.

Output

Print, in lexicographic order, the objects that can result from applying commands to Baba one or more times. If no command can be applied, print nothing.

Examples4

Example 1
Input
```
1
Rabbit is Carrot
```
Expected output

Example 2

Input

3
Rabbit is Carrot
Baba is Cat
Cat is Rabbit

Expected output

Carrot
Cat
Rabbit

Example 3
Input
```
1
Baba is Rabbit
```
Expected output
```
Rabbit
```

Example 4

Input

4
Baba is Rabbit
Rabbit is Cat
Cat is Wall
Wall is Unist

Expected output

Cat
Rabbit
Unist
Wall