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:35:32

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Miłosny wielokąt

Jak wszyscy wiemy, serialowe tasiemce z dużą obsadą często prowadzą do bardzo skomplikowanych związków. W jednym z takich seriali mamy $N$ postaci. Każda z tych postaci kocha dokładnie jedną postać (być może siebie). Dwie (różne) postacie są w związku wtedy i tylko wtedy, kiedy kochają się wzajemnie.

Oczywiście może to doprowadzić do pewnych skomplikowanych sytuacji, które nazywamy ,,miłosnymi wielokątami”. Powiemy, że 3 lub więcej osób jest w ,,miłosnym wielokącie”, kiedy pierwsza osoba kocha drugą, druga kocha trzecią, i tak dalej, aż wreszcie ostatnia osoba kocha pierwszą.

Ostatnie badania ankietowe pokazały, że widowni powoli nudzą się takie dramaty i pragną czegoś bardziej romantycznego. Dlatego zdecydowano, aby wystrzelić kilka magicznych strzał Amora w taki sposób, aby każdy był w związku. Za pomocą magicznej strzały Amora możemy zdecydować kogo kocha dana osoba (zmienić ją na dowolną inną).

Jaka jest minimalna liczba trafień strzałą Amora, aby tak się stało?

Input

Pierwszy wiersz wejścia zawiera pojedynczą liczbę całkowitą $N$, liczbę postaci w serialu. Następne $N$ wierszy zawiera po dwa imiona $s$ i $t$, oddzielone spacją, oznaczające że postać o imieniu $s$ początkowo kocha postać o imieniu $t$. Imiona bohaterów zawierają nie więcej niż 10 znaków i składają się wyłącznie z małych liter alfabetu łacińskiego.

Output

Na wyjście wypisz jedną liczbę całkowitą – minimalną liczbę strzał, które trzeba użyć, aby wszyscy znaleźli się w związku. Jeżeli nie jest to możliwe, wypisz $-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$

Każdy jest przez kogoś kochany $\heartsuit $ (być może przez samego siebie).

3

29

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

Nie ma żadnych związków, ani “miłosnych wielokątów”.

4

25

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

 

Explanation of Samples

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

Pierwszy przykład jest zilustrowany na obrazku powyżej. Górna część pokazuje początkową sytuację miłosną, gdzie strzałka z $s$ do $t$ oznacza, że $s$ początkowo kocha $t$, a różowym kolorem zaznaczone są trzy postacie, które muszą zostać trafione strzałą amora w optymalnym (i unikatowym) rozwiązaniu. Dolna część obrazka pokazuje sytuację po tych strzałach.

W drugim przykładzie (który spełnia ograniczenia trzeciego podzadania) jest kilka optymalnych rozwiązań. Jednym z nich jest trafienie strzałą amora bohaterów a, b oraz d i spowodowanie, aby zakochali się odpowiednio w b, a oraz c.

W trzecim przykładzie mamy miłosny trójkąt, dla którego niezależnie od tego, ile razy strzelimy strzałą Amora, zawsze ktoś zostanie samotny.

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