#P1682. 过家家

过家家

题目描述

2n2n 个小学生来玩过家家游戏,其中有 nn 个男生,编号为 11nn,另外 nn 个女生,编号也是 11nn。每一个女生可以先选择一个和她不吵嘴的男生来玩,除此之外,如果编号为 XX 的女生的朋友(也是女生,且编号为 YY)不和编号为 ZZ 的男生吵嘴,那么 XX 也可以选择 ZZ。此外,朋友关系是可以传递的,比如 aabb 是朋友,bbcc 是朋友,那么我们可以认为 aacc 也是朋友。

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

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

输入格式

第一行有四个整数 n,m,k,fn,m,k,f3n2503 \le n \le 2500<m<n20 < m < n^{2}0f<n0 \le f < n)。

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

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

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

输出格式

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

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

3