题目描述

题目译自 BalticOI 2018 Day1「Love Polygon」

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

输入格式

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

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

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

输出格式

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

提示

样例 1 解释

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

样例 2 解释

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

样例 3 解释

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