[AdditionalFile2774.zip](file://AdditionalFile2774.zip?type=additional_file)

#2774. 「BalticOI 2018」多角恋

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 BalticOI 2018 Day1「Love Polygon」

给一张 $N$ 个点的有向图，每次可以花费 $1$ 的代价修改图上的一条边的终点。求最少需要花费多少代价，才能使这张图形成若干个两两不相交的二元环，并且图上的所有点都在某一个环里。

输入格式

第一行包含一个整数 $N$。

接下来的 $N$ 行每行包含两个字符串 $s$ 和 $t$，表示图中存在一条 $(s\rightarrow t)$ 的边。

字符串只包含小写英文字母，且长度不超过 $10$。

输出格式

输出一个整数，表示最少需要花费多少代价，才能使这张图形成若干个两两不相交的环，并且图上的所有点都在某一个环里。无解请输出 $-1$。

样例 1

输入

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

输出

3

唯一的最优解如上图所示，图的上半部分为原图，底色为粉色的三个点为需要修改的边的起点；图的下半部分表示修改后的情况。

样例 2

输入

4
a
c
b c
c d
d d

输出

3

存在多组最优解。其中一种是分别改变一条以 a、b 和 d 为起点的边，使他们分别连接到 b、a 和 c。

样例 3

输入

3
rocky scarlet
scarlet patrick
patrick rocky

输出

-1

图中有 $3$ 个点，无论如何修改边的终点，总会有一个人不在环里。

数据范围与提示

请注意在 LibreOJ 上共有 $5$ 个子任务，其中第一个子任务为样例。