Description

There are $2n$ elementary school students playing the “playing house” game: $n$ boys labeled $1$ to $n$, and $n$ girls labeled $1$ to $n$. Each girl may choose a boy with whom she does not quarrel as her partner. In addition, if girl $X$ has a friend (also a girl) $Y$ who does not quarrel with boy $Z$, then $X$ may also choose $Z$. Moreover, friendship is transitive: if $a$ and $b$ are friends, and $b$ and $c$ are friends, then $a$ and $c$ are also considered friends. Note that a boy may be chosen by multiple girls as their partner.

Once every girl has chosen a partner, they start a new round of the game. After each round, every girl looks for a new boy as her partner (one she has never chosen before). Also, each girl may, in total, force at most $k$ boys to accept her, regardless of whether they have quarreled before.

Your task is to determine the maximum number of rounds the $2n$ students can play.

Input Format

The first line contains four integers $n, m, k, f$ (Constraints: $3 \le n \le 250$, $0 < m < n^{2}$, $0 \le f < n$).

Here, $n$ means there are $2n$ students in total, with $n$ boys and $n$ girls.

The next $m$ lines each contain two integers $a, b$, indicating that girl $a$ and boy $b$ have never quarreled.

The next $f$ lines each contain two integers $c, d$, indicating that girls $c$ and $d$ are friends.

Output Format

For each test, output one integer, the maximum number of rounds the $2n$ students can play.

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

3

Hint

Translated by ChatGPT 5