logo AlgoBeat OnlineJudge
登录 注册

#200669. 过家家

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

个小学生来玩过家家游戏,其中有 个男生,编号为 ,另外 个女生,编号也是 。每一个女生可以选择一个和她不吵嘴的男生来玩,除此之外,如果编号为 的女生的朋友(也是女生,且编号为 )不和编号为 的男生吵嘴,那么 也可以选择 。此外,朋友关系是可以传递的,比如 是朋友, 是朋友,那么我们可以认为 也是朋友。注意,一个男生可以被多个女生选择为玩伴。

当每一位女生都选择了玩伴,那么他们会开始新一轮游戏。在每一轮后,每个女生都会开始去找一个新的男生做玩伴(以前没选过)。而且每一个女生最多能强制 个男生接受,无论他们以前是否吵嘴。

现在你的任务就是确定这 个小学生最多能玩几轮游戏。

输入格式

第一行有四个整数 )。

表示有 个小学生,其中 个男生 个女生。

接下来 行,每行包含两个数字 表示编号为 的女生和编号为 的男生从没吵嘴过。

再接下来 行,每行包含两个数字 表示编号为 的女生和编号为 的女生是朋友。

输出格式

对于每组数据,输出一个整数,表示 个小学生最多能玩几轮。

样例

样例输入 1

4 5 1 2
1 1
2 3
3 2
4 2
4 4
1 4
2 3

样例输出 1

3