P1231 Composition of Study Aids

HansBug, who had been kicked out, was tidying up old Chinese textbooks when he discovered something curious.

In a Chinese textbook, HansBug found an answer key, but he clearly remembered that the book should also come with a workbook. However, there are too many items in front of him to count, including books, answer keys, and workbooks. A complete set should contain and only contain one book, one workbook, and one answer key, but everything is in a mess now. Although many labels have faded, HansBug can still roughly tell whether an item is a book, a workbook, or an answer key. He also roughly knows the possible correspondences between a book and an answer key, and between a book and a workbook (that is, he only knows which book and which answer key, and which book and which workbook could possibly correspond; all other pairs are impossible). Given this information, HansBug wants to know the maximum number of complete sets that can be formed simultaneously.

The first line contains three positive integers $N_1,N_2,N_3$, representing the numbers of books, workbooks, and answer keys respectively. The second line contains a positive integer $M_1$, representing the number of possible correspondences between books and workbooks. Each of the next $M_1$ lines contains two positive integers $x,y$, indicating that book $x$ and workbook $y$ could correspond. ($1\leq x \leq N_1$, $1 \leq y \leq N_2$) The next line contains a positive integer $M_2$, representing the number of possible correspondences between books and answer keys. Each of the next $M_2$ lines contains two positive integers $x,y$, indicating that book $x$ and answer key $y$ could correspond. ($1 \leq x \leq N_1$, $1 \leq y \leq N_3$)

Output a single positive integer, the maximum possible number of complete sets.

Sample explanation: As described, $N_1=5$, $N_2=3$, $N_3=4$, meaning there are $5$ books, $3$ workbooks, and $4$ answer keys. $M_1=5$, meaning there are $5$ possible correspondences between books and workbooks, namely: book $4$ with workbook $3$, book $2$ with workbook $2$, book $5$ with workbook $2$, book $5$ with workbook $1$, and book $5$ with workbook $3$. $M_2=5$, meaning there are $5$ possible correspondences between books and answer keys, namely: book $1$ with answer key $3$, book $3$ with answer key $1$, book $2$ with answer key $2$, book $3$ with answer key $3$, and book $4$ with answer key $3$. Therefore, at most two complete sets can be formed simultaneously in this case, namely: book $2$ + workbook $2$ + answer key $2$, and book $4$ + workbook $3$ + answer key $3$. Constraints: - For testdata points $1,2,3$, $1\le M_1,M_2\leq 20$. - For testdata points $4\sim 10$, $1\le M_1,M_2 \leq 20000$. Translated by ChatGPT 5