Problem I
Kjærlighetspolygon

Som vi alle vet så kan såpeoperaer på TV med mange karakterer ha ufattelig kompliserte kjærlighetsdramer. I en TV-serie så er det $N$ karakterer. Hver karakter elsker nøyaktig én karakter (som kan være han- eller hun selv). Vi sier at to karakterer er i et forhold hvis og bare hvis de elsker hverandre.

En spesiell type komplikasjon kalles et “kjærlighetspolygon”. Vi sier at 3 eller flere karakterer er i et “kjærlighetspolygon” hvis den første karakteren elsker den andre, den andre elsker den tredje, osv. - og også den siste karakteren elsker den første.

Nylige seerundersøkelser har avslørt at seerene har blitt lei av så mye drama og vil heller ha noe mer romantisk. Derfor har det blitt besluttet å skyte noen av karakterene med kjærlighetspiler slik at alle ender opp i forhold. Ved å skyte noen med en kjærlighetspil så kan du endre hvem den karakteren elsker (til en karakter av ditt valg).

Hva er det minste antall kjærlighetspiler som trengs for å få alle i et forhold?

Input

Første linje av input inneholder et heltall $N$, antall karakterer involvert. De neste $N$ linjene alle inneholder to navn skilt ved mellomrom, $s$ og $t$, som betyr at karakteren med navn $s$ til å begynne med elsker karakteren ved navn $t$. Navnene på karakterene er på ikke mer enn $10$ bokstaver og består kun av små bokstaver fra det engelske alfabetet (a til z).

Output

Skriv ut ett heltall – det minste antall kjærlighetspiler som trengs for å få alle inn i et forhold. Dersom dette ikke er mulig, skriv ut -1.

Begrensninger

Løsningen din vil bli testet på et sett av testgrupper, hver verdt et visst antall poeng. Hver testgruppe inneholder et sett av tester. For å få poeng for en testgruppe må du løse alle testene i den gruppen. Din endelige poengsum vil være den høyeste poengsummen du har fått på en enkelt innlevering.

Eksempelforklaring

Det første eksempelet er vist i illustrasjonen over. Den øvre seksjonen viser den opprinnelige situasjonen, med en pil pekende fra $s$ til $t$ for å indikere at $s$ opprinnelig elsker $t$, og den rosa fargen markerer de tre karakterene som må bli skutt med kjærlighetspiler i den unike optimale løsningen. Den nedre seksjonen viser situasjonen etterpå.

I det andre eksemplet (som tilfredsstiller begrensningene i gruppe 3) så er det flere forskjellige optimale løsninger. En av de er å skyte a, b og d med kjærlighetspiler, og å få de til å forelske seg i henholdsvis b, a og c.

I det tredje eksempelet har vi et kjærlighetstriangel, hvor uansett hvor mange piler vi skyter så vil alltid noen være utelatt.

8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

3

4
a c
b c
c d
d d

3

3
rocky scarlet
scarlet patrick
patrick rocky

-1