Complete Book Set Assembly

HansBug has encountered a disorganized collection of items: some books, some exercise books, and some answer sheets. He remembers that a complete book set should consist of exactly one book, one exercise book, and one answer sheet. However, due to the mess, the items are all mixed up. Fortunately, HansBug can roughly identify the type of each item (i.e. whether it is a book, an exercise book, or an answer sheet) and he also knows the potential pairing relationships: for some book b, he knows which answer sheet(s) a might belong to it and which exercise book(s) e might belong to it. (Any answer or exercise not connected to b is not possible to be paired with that book.)

Your task is to compute the maximum number of complete book sets that can be formed. A complete set is defined as a triple (book, answer, exercise) such that:

• The answer is paired with the book (i.e. there is an edge between them in the book‐answer relation),
• The exercise is paired with the same book (i.e. there is an edge between them in the book‐exercise relation),
• Each book, answer and exercise can be used in at most one set.

It turns out that the maximum number of complete sets equals the maximum number of books that can be simultaneously matched to both an answer sheet and an exercise book. One can show that this number is exactly \[ T = \min\{M_1, M_2\}, \] where \(M_1\) and \(M_2\) are the sizes of the maximum matchings in the book–answer and book–exercise bipartite graphs respectively. You are to compute \(T\).

inputFormat

The input begins with a line containing five integers n, m, k, p and q:

• n: the number of books.
• m: the number of answer sheets.
• k: the number of exercise books.
• p: the number of possible book–answer pairs.
• q: the number of possible book–exercise pairs.

Then follow p lines. Each line contains two integers b and a (1-indexed) indicating that book b can be paired with answer sheet a.

After that, there are q lines. Each line contains two integers b and e (1-indexed) indicating that book b can be paired with exercise book e.

It is guaranteed that all numbers are positive and the edges are given without duplication.

outputFormat

Output a single integer, the maximum number of complete book sets that can be formed.

Note: Use standard matching algorithms. In our formulation, the answer is \(T = \min(M_1, M_2)\) where the matchings are computed on the bipartite graphs: (books, answers) and (books, exercises) respectively.

sample

3 3 3 3 3
1 1
2 2
3 3
1 1
2 2
3 3

3