|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||46||6||6||13.043%|
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, animals have to check in with a guard. The guard writes down the animal species, and then the animal is allowed to join the end of the line, in last position. At the other end of the line, animals have to check out: when the animal in first position in the line is finally allowed to enter the hunting-free area, another guard writes down the animal species. Thus, each guard maintains a list of animal species, written down in the chronological order in which the animals have checked in or out. A total of N animals, representing S species, have checked in (and, therefore, checked out).
However, animals may enter the waiting line and leave it in different orders. Indeed, some animal species are friends with each other, and thus two animals from such species, if they occupy adjacent places in the line, may accept to switch their places.
You have a list of those pairs of animal species that may accept to switch their places when being in adjacent positions in the line: this list contains L pairs. You were handed out the check-in list maintained by the first guard. Depending on which animals decided to switch places, several checkout lists might be possible. Among all those possible lists, which one comes first in alphabetical order?
The input consists of the following lines:
The output should contain a single line containing N words w0, . . . , wN−1, separated by spaces: the list w0, . . . , wN−1 must be, among all the possible check-out lists, the one that comes first in alphabetical order.
3 2 6 ANTILOPE CAT ANT CAT ANTILOPE ANTILOPE ANT ANT CAT CAT ANTILOPE CAT ANT
ANT ANTILOPE CAT CAT CAT ANT
The six possible orderings at check-out, sorted in (increasing) alphabetical order, are: