Problem D
Tag
Languages
en
sv
Every day, $N$ Chalmers student meet up at Kemigården to play tag. In this game, there is a hunter, and when this person tags another person, the other person becomes the hunter instead. After playing a couple of times, you realize that something is not right. Namely, you have noticed that there are suddenly many more hunters than there should be. If everyone follows the rules, there should always be exactly one hunter. However, the other day the game got out of hand, and suddenly you had a dozen bloodthirsty engineering students chasing you.
You have realized that some students must be tagging other people even though they themselves are not hunters. Now you want to figure out which students have cheated in this way. A student cheats if they ever tag another student while knowing that they themselves are not a hunter. Luckily, yesterday you very carefully took down notes about both who participated in the games, and who tagged who. After collecting this information you are now going to write a program that tells you which students cheated.
Input
The first line contain two integers $N$ and $M$ ($2 \leq N \leq 10^5$, $1 \leq M \leq 10^5$), representing the number of students who participated in the game and the number of times one student tagged another.
Following that, there is a line with space-separated names $s_1, ..., s_ N$ of the students who participated in the game. Each name consists of 1-20 characters and only contains the letters a-z. All names are unique. The first name in this list is the person who started as the hunter.
Finally, there are $M$ lines, where each line is in the form “$s_ i$ tar $s_ j$”, with $s_ i \neq s_ j$, which means that $s_ i$ has tagged $s_ j$. These lines indicate in chronological order which students tagged each other. Since you observed the game very carefully, you are sure that you did not miss any tags.
Output
First write an integer, the number of students who cheated. After that, on a new line, write the names of the students who cheated, sorted in alphabetical order.
Scoring
Your solution will be tested on a number of sample groups. To get points in a group your solution must pass all test cases in that group.
|
Group |
Point value |
Constraints |
|
$1$ |
$10$ |
$M = 1$ |
|
$2$ |
$15$ |
$N = 2$ |
|
$3$ |
$15$ |
joshua is playing, and either no one cheats or only joshua cheats. |
|
$4$ |
$20$ |
$N \leq 200$ |
|
$5$ |
$40$ |
No further constraints. |
Explanation of sample case 1
At the beginning, olle is the hunter. This means that alexander cheats when he tags joshua. After that, both olle and joshua believe that they are the hunter. Since joshua thinks he is the hunter, he is not cheating when he tags alexander. Finally, olle tags joshua, and after that joshua and alexander believe that they are hunters. The conclusion is the only who cheated was alexander.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 olle joshua alexander alexander tar joshua joshua tar alexander olle tar joshua |
1 alexander |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 7 nils olle joshua fredrik alexander nils tar olle nils tar fredrik nils tar alexander joshua tar nils alexander tar nils fredrik tar nils olle tar nils |
2 joshua nils |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 4 olle joshua alexander alexander tar olle joshua tar alexander olle tar joshua olle tar alexander |
3 alexander joshua olle |
| Sample Input 4 | Sample Output 4 |
|---|---|
4 4 anna bosse carina dagmar anna tar bosse bosse tar carina carina tar dagmar dagmar tar anna |
0 |
