#2774. 「BalticOI 2018」多角恋

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mingqi_H

题目描述

题目译自 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

样例输出 1

3

样例 1 解释

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

样例输入 2

4
a
c
b c
c d
d d

样例输出 2

3

样例 2 解释

存在多组最优解。其中一种是分别改变一条以 abd 为起点的边,使他们分别连接到 bac

样例输入 3

3
rocky scarlet
scarlet patrick
patrick rocky

样例输出 3

-1

样例 3 解释

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

数据范围与提示

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

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