Hide

Problem B
Jage

Languages en sv

På Kemigården brukar $N$ chalmerister träffas varje dag och leka jage. Leken går ut på att en person är jagare, och när denne sedan tar en annan person genom att nudda personen blir den tagna personen jagare istället. Efter att ha varit med och lekt några gånger har du insett att något inte står rätt till. Du har nämligen märkt att det plötsligt finns många fler jagare än vad det borde. Om alla håller sig till reglerna borde det alltid finnas exakt en jagare, men häromdagen gick leken överstyr och du hade plötsligt ett dussin blodtörstiga datastudenter efter dig.

Du har insett att det måste vara så att vissa studenter tar andra trots att de inte själva är jagare. Nu vill du lista ut vilka studenter det är som fuskar på det här sättet. En student fuskar ifall de tar någon när de vet att de själva inte är jagare. Som tur är var du väldigt noggrann igår, och förde protokoll över både vilka som deltog i leken, och vem som tog vem. Efter att ha samlat in denna information ska du nu skriva ett program som berättar vilka studenter som har fuskat.

Indata

Den första raden innehåller två heltal $N$ och $M$ ($2 \leq N \leq 10^5$, $1 \leq M \leq 10^5$), antalet studenter som deltog i leken och antalet gånger någon student tog en annan.

Därefter följer en rad med de mellanslagsseparerade namnen $s_1, ..., s_ N$ på de studenter som deltog i leken. Varje namn består av 1-20 tecken, och innehåller endast bokstäverna a-z. Alla namn är unika. Det första namnet i denna lista är personen som började som jagare.

Därefter följer $M$ rader, där varje rad är på formen “$s_ i$ tar $s_ j$”, där $s_ i \neq s_ j$. Dessa anger i kronologisk ordning vilka studenter som tar varandra. Eftersom du kollade väldigt noga vet du att du inte missade någon tagning.

Utdata

Skriv först ut ett heltal, antalet studenter som fuskade. Skriv därefter på en ny rad ut namnen på de studenter som fuskade, sorterade i alfabetisk ordning.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poäng

Gränser

$1$

$10$

$M = 1$.

$2$

$15$

$N = 2$

$3$

$15$

joshua är med i leken, och om någon fuskar så är det han.

$4$

$20$

$N \leq 200$.

$5$

$40$

Inga ytterligare begränsningar.

Förklaring av testfall 1

Från början är det olle som är jagare. Det betyder att alexander fuskar när han tar joshua. Efter det tror både olle och joshua att de är jagare. Eftersom joshua tror att han är jagare fuskar han inte när han tar alexander. Till slut tar olle joshua, och det är då joshua och alexander som tror att de är jagare. Slutsatsen är att endast alexander fuskade.

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