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