LibreOJ

2774 「BalticOI 2018」多角恋

内存限制：1024 MB 时间限制：2000 ms

题目描述

题目译自 BalticOI 2018 Day1「Love Polygon」

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

输入格式

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

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

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

输出格式

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

样例 1

gg.svg

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

样例 2

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

样例 3

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

数据范围与提示

子任务 分值 数据范围 附加限制
$1$ $21$ $2\leqslant N\leqslant 20$
$2$ $25$ $2\leqslant N\leqslant 100\, 000$ 每个点都有一条入边（可能有自环）
$3$ $29$ $2\leqslant N\leqslant 100\, 000$ 不存在两个点或更多个点构成的环
$4$ $25$ $2\leqslant N\leqslant 100\, 000$

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

样例

样例输入 1

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

样例输出 1

3

样例输入 2

4
a
c
b c
c d
d d

样例输出 2

3

样例输入 3

3
rocky scarlet
scarlet patrick
patrick rocky

样例输出 3

-1