Hide

Problem B
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