Problem Description

This problem is translated from BalticOI 2018 Day 1 “Love Polygon”.

You are given a directed graph with $N$ vertices, where each vertex has out-degree $1$. Each time, you may pay a cost of $1$ to change the destination of one edge in the graph, i.e., change which vertex is reached from a given starting vertex. Find the minimum total cost needed to make the graph become several pairwise disjoint 2-cycles, and every vertex in the graph must belong to some cycle.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain two strings $s$ and $t$, meaning there is an edge $s\rightarrow t$ in the graph.

Each string contains only lowercase English letters and has length at most $10$.

Output Format

Output one integer, the minimum total cost needed to make the graph become several pairwise disjoint 2-cycles, and every vertex in the graph must belong to some cycle. If there is no solution, output $-1$.

8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

3

4
a c
b c
c d
d d

3

3
rocky scarlet
scarlet patrick
patrick rocky

-1

Hint

Explanation for Sample 1

The only optimal solution is shown in the figure above. The upper part is the original graph, and the three vertices with a pink background are the starting vertices of the edges that need to be modified. The lower part shows the graph after the modifications.

Explanation for Sample 2

There are multiple optimal solutions. One of them is to change the edges starting from a, b, and d, so that they connect to b, a, and c, respectively.

Explanation for Sample 3

There are $3$ vertices in the graph. No matter how you change the destinations of edges, there will always be one person not in any cycle.

Translated by ChatGPT 5