Problem E
Match-fixing
Languages
en
sv
Lola and her $N-1$ classmates always play table tennis during recess. Now, Lola wants to crown the class’s table tennis champion, and since there is only one ping pong table, it works as follows: There are $N-1$ matches, and everyone waits in line for their turn to play. The winner of each match stays at the table to face the next person in line. The person who wins the last match is crowned the class’s table tennis champion.
Lola loves both table tennis and statistics, so she has kept track of the results of all table tennis matches ever played between her classmates. Therefore, she always knows who will win when two people face each other. It is also guaranteed that there will always be a winner, a match can never end in a draw. Now, she wants to use this information to create a queue order such that she herself becomes the table tennis champion, regardless of what happens. Given who wins over whom, can you help Lola create such a queue order?
Input
The first line contains an integer $N$ ($2 \leq N \leq 1000$), which is the number of people in Lola’s class. Then follow $N$ descriptions of the people. Each description consists of two lines. The first line contains the person’s name and how many people they win over. The second line contains the names of all the people they win over.
All names are strings that are a maximum of $20$ characters long and consist only of lowercase letters from the English alphabet. It is guaranteed that no two people have the same name, and the name "lola" is always included in the input.
Output
Print a queue order such that Lola becomes the table tennis champion. If there are multiple valid orders, you may print any of them. If no such order exists, print $-1$.
Scoring
Your solution will be tested on several different test groups. To earn points for a group, you must pass all test cases in the group.
|
Group |
Points |
Constraints |
|
$1$ |
$14$ |
$N = 10$ |
|
$2$ |
$17$ |
$N = 20$ |
|
$3$ |
$20$ |
$N = 100$ |
|
$4$ |
$49$ |
No additional constraints. |
Explanation
In the first example case, we can first have Beata face Anna. Then Beata will win. Afterward, Beata can face Lola, and Lola will win. Therefore, the queue order Anna - Beata - Lola works.
In the second example case, Beata will win no matter who she faces. Therefore, it is impossible to create a queue order.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 anna 1 lola beata 1 anna lola 1 beata |
anna beata lola |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 anna 2 beata lola beata 0 lola 1 beata |
Impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 lola 2 david angela david 2 bobo angela casper 2 lola david angela 2 bobo casper bobo 2 casper lola |
david bobo casper angela lola |
