Description
Floryan is a pretty busy, and he is always trying to man-age his schedule. However, it becomes di cult when some items on his to-do list have dependencies. For example, he absolutely will NOT watch The Empire Strikes Back with his kids before watching A New Hope with them. Because of these dependencies, ordering tasks can be quite di cult. Given Floryan’s tasks and the dependencies that exist, pro-duce an order of performing those tasks that is valid.
Input
The input le will consist of one test case. The rst line will contain a two numbers t 104 and d 106, denoting the number tasks and the number of dependencies between them. The next t lines will list each task as a string with no spaces. The d lines after that will list the dependences,
two per line. These lines indicate that task 1 (the rst task listed) is required to be complete before task 2.
Output
For each test case, output a possible ordering of the tasks that Floryan can use or the string “IMPOSSIBLE” if there are no such orderings. If there are multiple solutions, list the one that comes rst lexicographically.
Sample Input
|
4 3 |
|
|
groceryshopping |
Sample Output |
|
pickupkids |
|
|
cookdinner |
groceryshopping pickupkids cookdinner |
|
bedtime |
bedtime |
|
groceryshopping cookdinner |
|
|
pickupkids cookdinner |
|
|
cookdinner bedtime |
1
