Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-27 23:00 AKDT

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 04:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -952 days 18:04:13

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?

Wejście

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.

Wyjście

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$.

Ograniczenia

Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, Twoje rozwiązanie musi przejść wszystkie testy z tej grupy. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.

Grupa

Punkty

Limity

Dodatkowe ograniczenia

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$

 

Wyjaśnienie do przykładów

\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.

Przykładowe wejście 1 Przykładowe wyjście 1
8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia
3
Przykładowe wejście 2 Przykładowe wyjście 2
4
a c
b c
c d
d d
3
Przykładowe wejście 3 Przykładowe wyjście 3
3
rocky scarlet
scarlet patrick
patrick rocky
-1