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

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Многоугольник любви

Как мы все знаем, любовные отношения между персонажами телевизионных мыльных опер нередко бывают довольно запутанными. В одном телесериале имеется $N$ персонажей. Каждый из них любит ровно одного персонажа (причем этим персонажем может быть он сам).

Будем говорить, что два персонажа находятся в отношениях, если они взаимно любят друг друга. Иногда встречается более сложная конфигурация отношений под названием «любовный многоугольник». Будем говорить, что 3 или более персонажей находятся в «любовном многоугольнике», если первый персонаж любит второго, второй любит третьего, и так далее до последнего, который любит первого.

Недавние опросы показали, что телезрителям надоели драмы, и они бы предпочли более романтический сюжет, в котором все персонажи находятся во взаимных отношениях.

По сценарию можно изменить то, кого любит тот или иной персонаж, выстрелив в него «стрелой любви». Помоги сценаристам достичь ситуации, где все персонажи во взаимных отношениях, выстрелив наименьшее возможное количество «стрел любви».

Ввод

На первой строке дано целое число $N$ – число персонажей телесериала. На каждой из следующих $N$ строк даны два разделенных пробелом имени $s$ и $t$, указывающих что персонаж по имени $s$ изначально любит персонажа по имени $t$. Все имена персонажей состоят из прописных латинских букв и не длиннее $10$ символов.

Вывод

Вывести одно целое число – минимальное число стрел любви, которое нужно выстрелить, чтобы все персонажи оказались во взаимных отношениях. Если это невозможно, вывести $-1$.

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Группа

Очки

Ограничения

Дополнительные ограничения

1

21

$2 \le N \le 20$

 

2

25

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

Каждого персонажа кто-то любит.

3

29

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

Отсутствуют отношения или «любовные многоугольники».

4

25

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

 

Объяснение примеров

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

Первый пример проиллюстрирован на рисунке выше. Верхняя часть – изначальная конфигурация отношений, где стрелка, ведущая от $s$ к $t$, указывает, что $s$ изначально любит $t$, а розовым цветом отмечены три персонажа, в которых нужно выстрелить стрелами любви, чтобы получить единственное оптимальное решение. Нижняя часть рисунка иллюстрирует результат.

Во втором примере (который удовлетворяет условиям группы тестов 3) имеется несколько оптимальных решений. Одно из них – выстрелить в a, b и d, и заставить их влюбиться в b, a и c, соответственно.

В третьем примере показан любовный треугольник, где, сколько ни стреляй, кто-нибудь всегда останется лишним.

Пример ввода 1 Пример вывода 1
8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia
3
Пример ввода 2 Пример вывода 2
4
a c
b c
c d
d d
3
Пример ввода 3 Пример вывода 3
3
rocky scarlet
scarlet patrick
patrick rocky
-1