过家家

题目描述

有 $2n$ 个小学生来玩过家家游戏,其中有 $n$ 个男生,编号为 $1$ 到 $n$,另外 $n$ 个女生,编号也是 $1$ 到 $n$。每一个女生可以选择一个和她不吵嘴的男生来玩,除此之外,如果编号为 $X$ 的女生的朋友(也是女生,且编号为 $Y$)不和编号为 $Z$ 的男生吵嘴,那么 $X$ 也可以选择 $Z$。此外,朋友关系是可以传递的,比如 $a$ 和 $b$ 是朋友,$b$ 和 $c$ 是朋友,那么我们可以认为 $a$ 和 $c$ 也是朋友。注意,一个男生可以被多个女生选择为玩伴。 当每一位女生都选择了玩伴,那么他们会开始新一轮游戏。在每一轮后,每个女生都会开始去找一个新的男生做玩伴(以前没选过)。而且每一个女生最多能强制 $k$ 个男生接受,无论他们以前是否吵嘴。 现在你的任务就是确定这 $2n$ 个小学生最多能玩几轮游戏。

输入输出格式

输入格式


第一行有四个整数 $n,m,k,f$($3 \le n \le 250$,$0 < m < n^{2}$,$0 \le f < n$)。 $n$ 表示有 $2n$ 个小学生,其中 $n$ 个男生 $n$ 个女生。 接下来 $m$ 行,每行包含两个数字 $a,b$ 表示编号为 $a$ 的女生和编号为 $b$ 的男生从没吵嘴过。 再接下来 $f$ 行,每行包含两个数字 $c,d$ 表示编号为 $c$ 的女生和编号为 $d$ 的女生是朋友。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3