AT_abc190_c [ABC190C] Bowls and Dishes

有 $N$ 个编号为 $1, 2, \dots, N$ 的盘子，以及 $M$ 个编号为 $1, 2, \dots, M$ 的条件。 条件 $i$ 表示：当盘子 $A_i$ 和盘子 $B_i$ 上都至少有一个球时，该条件被满足。 有 $K$ 个人，编号为 $1, 2, \dots, 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$

请输出最大能满足的条件数。

## 限制条件 - 所有输入均为整数。 - $2 \leq N \leq 100$ - $1 \leq M \leq 100$ - $1 \leq A_i < B_i \leq N$ - $1 \leq K \leq 16$ - $1 \leq C_i < D_i \leq N$ ## 样例解释 1 例如，如果第 $1, 2, 3$ 个人分别将球放在盘子 $1, 3, 2$ 上，则可以满足条件 $1, 2$，共 $2$ 个条件。 ## 样例解释 2 例如，如果第 $1, 2, 3, 4$ 个人分别将球放在盘子 $3, 1, 2, 4$ 上，则可以满足所有条件。 由 ChatGPT 4.1 翻译