Problem Description

This problem is a translation from BalticOI 2018 Day1「Love Polygon」

Given a directed graph with $N$ vertices, where each vertex has an outdegree of $1$. You can spend $1$ cost to modify the destination of an edge in the graph, i.e., change the vertex that a vertex points to. Determine the minimum cost required to transform the graph into several disjoint binary cycles, such that all vertices are part of at least one cycle.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain two strings $s$ and $t$, indicating an edge from $s$ to $t$ in the graph.

The strings consist only of lowercase English letters and have a length not exceeding $10$.

Output Format

Output a single integer, which is the minimum cost required to transform the graph into several disjoint binary cycles, ensuring all vertices are part of at least one cycle. If it is impossible, output $-1$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

4
a c
b c
c d
d d

Sample Output #2

3

Sample Input #3

3
rocky scarlet
scarlet patrick
patrick rocky

Sample Output #3

-1

Notes

Sample 1 Explanation

The only optimal solution is shown in the diagram above. The upper part represents the original graph, with the three pink-colored vertices indicating the starting points of the edges that need to be modified. The lower part shows the modified graph.

Sample 2 Explanation

There are multiple optimal solutions. One is to change the edges starting from a, b, and d to point to b, a, and c, respectively.

Sample 3 Explanation

The graph has 3 vertices, and no matter how the destination of the edges is modified, there will always be one vertex not in a cycle.

见题面 Input 部分

见题面 Output 部分