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 -225 days 23:44:51

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Armastuse hulknurk

Nagu me kõik teame, on seebiooperite tegelased omavahel tõsiselt keerulistes suhetes. Ühes seebiooperis on $N$ tegelast, kellest igaüks armastab täpselt üht isikut. On ka võimalik, et tegelane armastab (alguses) ainult iseennast. Ütleme, et kaks tegelast on paarisuhtes, kui esimene armastab teist ja teine esimest.

Vahel tekib eriti keeruline suhe, mida nimetatakse “armastuse hulknurgaks”. Ütleme, et 3 või enam inimest on “armastuse hulknurgas”, kui esimene armastab teist, teine kolmandat jne, kuni viimane isik armastab esimest.

Vaatajaküsitlused näitavad, et televaatajad on sellisest draamast väsinud nig eelistaks midagi romantilisemat. Meil on võimalik muuta, keda inimene armastab, tulistades teda armunoolega. Eesmärgiks on, et kõik isikud oleksid paarisuhetes.

Mis on minimaalne arv armunooli, mis selleks tuleb kulutada?

Input

Esimesel real on täisarv $N$, mis tähistab seebiooperi tegelaste arvu. Järgmistel $N$ real on igaühel kaks tühikuga eraldatud nime $s$ ja $t$, mis tähendavad, et tegelane $s$ armastab alguses tegelast $t$. Nimed on ülimalt $10$ tähe pikkused ja koosnevad ladina tähestiku väiketähtedest.

Output

Väljundisse kirjutada üks täisarv – minimaalne armunoolte arv, mis kindlustaks, et kõik tegelased on suhtes. Kui see ei ole võimalik, väljastada -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$

Iga isiku puhul leidub keegi, kes teda armastab (võimalik, et ta ise).

3

29

$2 \le N \le 100\, 000$

Alguses pole ühtki paarisuhet ega “armastuse hulknurka”.

4

25

$2 \le N \le 100\, 000$

 

Explanation of Samples

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

Esimene näide on toodud joonisel. Ülemine osa illustreerib algset olukorda, kus nool, mis näitab isikult $s$ isikule $t$, tähendab, et isik $s$ armastab alguses isikut $t$, ning roosa värv tähistab kolme isikut, keda tuleb optimaalse olukorra saavutamiseks tulistada. Alumine osa näitab lõppseisu.

Teises näites (mis rahuldab alamülesande 3 tingimusi) on mitu võimalikku lahendust. Üks võimalus on tulistada iskuid a, b and d, nii et nad hakkavad armastama isikuid b, a ja c.

Kolmandas näites on meil armastuse kolmnurk ja ükskõik, kuidas nooli lasta, jääb keegi alati välja.

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