영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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 ≤ N ≤ 10^5, 1 ≤ M ≤ 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 ≠ 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 set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | 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 ≤ 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.
예제
예제 1
3 3 olle joshua alexander alexander tar joshua joshua tar alexander olle tar joshua
1 alexander
예제 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
예제 3
3 4 olle joshua alexander alexander tar olle joshua tar alexander olle tar joshua olle tar alexander
3 alexander joshua olle
예제 4
4 4 anna bosse carina dagmar anna tar bosse bosse tar carina carina tar dagmar dagmar tar anna
0