碗与盘子

题目描述

有编号为 $1, 2, \dots, N$ 的 $N$ 个盘子和编号为 $1, 2, \dots, M$ 的 $M$ 个条件。

条件 $i$ 在盘子 $A_i$ 和盘子 $B_i$ 上都（至少 $1$ 个）放置了球时被满足。

有编号为 $1, 2, \dots, K$ 的 $K$ 个人，人 $i$ 在盘子 $C_i$ 或盘子 $D_i$ 中的其中一个上放置球。

最多能满足几个条件？

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$
$K$
$C_1$ $D_1$
$\vdots$
$C_K$ $D_K$

输出格式

输出答案。

样例

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

2

例如，人 $1, 2, 3$ 分别把球放在盘子 $1, 3, 2$ 上时，条件 $1, 2$ 这 $2$ 个被满足。

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

4

例如，人 $1, 2, 3, 4$ 分别把球放在盘子 $3, 1, 2, 4$ 上时，所有条件都被满足。

6 12
2 3
4 6
1 2
4 5
2 6
1 5
4 5
1 3
1 2
2 6
2 3
2 5
5
3 5
1 4
2 6
4 6
5 6

9

数据范围

• 输入均为整数
• $2 \le N \le 100$
• $1 \le M \le 100$
• $1 \le A_i \lt B_i \le N$
• $1 \le K \le 16$
• $1 \le C_i \lt D_i \le N$