Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-28 07:00 UTC

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 12:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -226 days 0:15:38

Time elapsed

5:00:00

Time remaining

0:00:00

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.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

Additional Constraints

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$

 

Explanation of Samples

\includegraphics[width=0.5\textwidth ]{polygonfig.pdf}

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