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:28:42

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Polygondrama

Som vi alla vet kan TV-serier med många personer innebära komplicerade kärleksdraman. I en viss TV-serie finns det $N$ personer. Varje person älskar exakt en person, vilket faktiskt kan vara den själv. Två personer är i ett parförhållande om och endast om de båda älskar varandra.

En specifik typ av komplicerat kärleksdrama kallas för “polygondrama”. Vi säger att $3$ eller fler personer är i ett “polygondrama” om den första personen älskar den andra, den andra älskar den tredje, och så vidare, samt att den sista personen älskar den första personen.

Undersökningar har visat att tittarna har blivit trötta på komplicerade kärleksdraman och skulle föredra något mer romantiskt. Därför bestämdes det att vissa personer ska skjutas med kärlekspilar så att alla hamnar i ett parförhållande. Genom att skjuta en person med en kärlekspil kan du välja att ändra vem den personen älskar till vem du vill.

Vad är det minsta antalet kärlekspilar som behövs för att alla ska hamna i ett parförhållande?

Input

Den första raden innehåller ett heltal $N$, antalet personer. Nästkommande $N$ rader innehåller två mellanslagsseparerade namn $s$ och $t$, vilket betyder att personen med namn $s$ älskar personen med namn $t$. Personernas namn kommer inte att innehålla fler än $10$ bokstäver, och alla bokstäver kommer vara små och ingå i det engelska alfabetet.

Output

Skriv ut ett heltal – det minsta antalet kärlekspilar som krävs för att alla ska vara i ett parförhållande. Om det inte är möjligt, 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$

Varje person är älskad av någon (möjligen av sig själv).

3

29

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

Det finns inga parförhållanden och inga “polygondraman”.

4

25

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

 

Explanation of Samples

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

Det första exemplet illustreras i figuren ovan. Den övre delen visar vem som älskar varandra från början, där en pil från $s$ till $t$ indikerar att $s$ älskar $t$, och den rosa färgen förtydligar de tre personerna som behöver skjutas med en kärlekspil i den unika optimala lösningen. Den undre delen visar situationen efter att kärlekspilarna har skjutits.

I det andra exemplet (som uppfyller kriterierna för testgrupp 3) finns det flera optimala lösningar. En av dessa är att skjuta a, b and d med kärlekspilar, och låta dem älska b, a respektive c.

I det tredje exemplet har vi ett “polygondrama”, och oavsett hur många kärlekspilar som skjuts kommer någon hamna utanför.

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