Problem G
Cykelmyggen Egon

Egon leder efter en cykeltur gennem den tætte underskov. En cykeltur går fra én plante til den næste osv., og ender samme sted som den starter. Sådan en tur kan Egon nemlig gentage i uendelighed.

Egon har modvilligt lovet Dansemyggen Dagmar en dans, så snart han er færdig med træningen. Denne forpligtelse pønser han på at kunne undgå ved at strække træningen så langt, at Dagmar bliver træt af at vente.

Dagmar har dog luret Egons plan om at lade træningen trække i langdrag og har ikke tænkt sig at lade ham slippe af sted med det. Hun sætter sig for at spolere Egons cykeltur.

Blandt det stærke myrefolk har Dagmar heldigvis gode venner, som hun kan bede om hjælp. Myrerne befinder sig ved bestemte planter i underskoven og kan på Dagmars kommando fjerne specifikke blade fra disse planter, så Egon ikke længere kan bruge dem på sin cykeltur. Af respekt for planterne vil hun dog ikke bede myrerne om at fjerne alle bladene fra en plante – det ville være synd.

I billedet foroven, med $4$ planter og $4$ blade, kan Egon cykle rundt lige så længe han vil mellem $1$, $3$, $2$, $1$, $3$, $\ldots $. Men hvis der er myrer på plante $3$, kan de spolere Egons cykeltur ved at spise bladet til plante $2$, hvilket tvinger ham videre til plante $4$. Her må turen standse og Egon danse.

Hvis Dagmars myrevenner derimod er på plante $1$ eller $2$ (eller begge), kan hun intet gøre: myrerne vil ikke spise plantens sidste blad.

Kan Dagmar og myrerne gøre det umuligt for Egon at finde en cykeltur og derved tvinge ham i danseskoene?

Indlæsning

Først en linje med et heltal $N$, hvor $1 \leq N \leq 50.000$, som angiver antallet af planter i underskoven.

Derefter følger $N$ linjer, hvor den $i$te linje beskriver den $i$te plante for $i = 1, 2, \ldots , N$. Hver linje begynder med to heltal $m_ i$ og $k_ i$. Hvis $m_ i=1$, så findes der myrer ved den $i$te plante, ellers er $m_ i=0$. Det andet heltal opfylder $0 \leq k_ i < N$ og angiver antallet af blade på planten, som fører videre til andre planter. På samme linje følger $k_ i$ heltal adskilte af mellemrum, som beskriver hvilke planter bladene fører til.

Du kan antage $k_1+\cdots + k_ N \leq 50.000$. Derudover vil et blad ikke føre til samme plante, som det starter ved, og to blade fra samme plante vil altid føre til forskellige planter.

Udskrift

Skriv »Dagmar«, hvis Dagmar kan gøre det umuligt for Egon at finde en cykeltur. Ellers skriv »Egon«.

Pointsætning

Der er 5 testgrupper.

Forklaring af eksempler

Eksempel 1

I eksempel $1$ kan Egon bruge cykelturen $1$, $3$, $2$, $1$, $\ldots $ lige så længe, han vil. Myrerne på de to planter lader nemlig det sidste blad på hver plante være i fred.

Eksempel 2

I eksempel $2$ vinder Dagmar. Hun kan nemlig bede myrerne ved plante $3$ om at spise bladet til plante $2$.

Eksempel 3

I eksempel $3$ er der slet ingen myrer, og Egon vinder på grund af cykelturen $1$, $2$, $3$, $1$, $\ldots $.

Eksempel 4

I eksempel $4$ er der heller ingen myrer, men heller ingen cykeltur. Uanset, hvor Egon begynder, må han afslutte sin træning senest på plante $2$.

Eksempel 5

I eksempel $5$ kan myrerne ved plante $3$ spise det ene af bladene, men ikke begge. Uanset, hvad de gør, vil der stadig være en cykeltur, så Egon vinder.

4
1 1 3
1 1 1
0 2 2 4
0 0

Egon

4
0 1 3
0 1 1
1 2 2 4
0 0

Dagmar

3
0 1 2
0 1 3
0 1 1

Egon

4
0 1 2
0 0
0 1 2
0 2 1 3

Dagmar

5
0 1 3
0 1 1
1 2 2 5
0 1 3
0 1 4

Egon