Problem A
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.
|
Group |
Points |
Limits |
Yttligere begrensninger |
|
1 |
21 |
$2 \le N \le 20$ |
|
|
2 |
25 |
$2 \le N \le 100\, 000$ |
Hver karakter er elsket av noen (muligens dem selv). |
|
3 |
29 |
$2 \le N \le 100\, 000$ |
Det er ingen forhold eller “kjærlighetspolygoner”. |
|
4 |
25 |
$2 \le N \le 100\, 000$ |
Eksempelforklaring
![\includegraphics[width=0.5\textwidth ]{polygonfig.pdf}](/problems/lovepolygon/file/statement/no/img-0001.png)
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 leonard emmy ada emmy isaac leonard emmy pierre pierre bernhard bernhard emmy sofia karl karl sofia |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 a c b c c d d d |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 rocky scarlet scarlet patrick patrick rocky |
-1 |
