Swapping Places

Animals are waiting in a line in a quarantine zone before they can enter a hunting-free area, where they will find an easier life.

When entering the quarantine zone, each animal checks in with a guard. The guard writes down the animal species, and the animal joins the end of the line, in last position. At the other end of the line, animals check out. When the animal in first position is finally allowed to enter the hunting-free area, another guard writes down its species. Each guard therefore keeps a list of species in the chronological order of check-ins or check-outs. A total of N animals, representing S species, check in and therefore check out.

However, animals may enter and leave the line in different orders. Some species are friends, so two animals from such species that occupy adjacent places in the line may agree to switch places.

You have a list of L pairs of species that may agree to switch places when they stand in adjacent positions. You are given the check-in list kept by the first guard. Depending on which animals decide to switch places, several check-out lists may be possible. Among all of them, which one comes first in alphabetical order?

The input consists of the following lines:

• Line 1 contains three space-separated integers S, L and N. S is the number of animal species, L is the number of pairs of species that are friends with each other, and N is the number of animals that entered the waiting line.
• The next S lines each contain the name of one species. Each name is a single word of uppercase letters from A to Z, with between 1 and 20 letters.
• The next L lines each contain two space-separated species names A and B, meaning that A and B are friends with each other.
• The last line contains N space-separated species names. The kth word is the species of the animal that entered the line in kth position.

Print a single line with N words $w_0, \ldots, w_{N-1}$, separated by spaces. The list must be the one that comes first in alphabetical order among all possible check-out lists.

• $1 \le S \le 200$
• $0 \le L \le 10\,000$
• $1 \le N \le 100\,000$

The six possible check-out orders, sorted in increasing alphabetical order, are:

1. ANT ANTILOPE CAT CAT CAT ANT
2. ANT CAT ANTILOPE CAT CAT ANT
3. ANT CAT CAT ANTILOPE CAT ANT
4. ANT CAT CAT CAT ANT ANTILOPE
5. ANT CAT CAT CAT ANTILOPE ANT
6. ANTILOPE ANT CAT CAT CAT ANT