루미 알고리즘

#1579골드Tag

PO 2024 결선코딩출제 Olle Lapidus영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
110M = 1
215N = 2
315joshua is playing, and either no one cheats or only joshua cheats.
420N ≤ 200
540No 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

출처 표기

출처: Programmeringsolympiaden 2024년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.