分数: 300 点
问题陈述
我们有 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.
最多满足几个条件?
约束
- 输入中的所有值都是整数。
- 2 ≤ N ≤ 100
- 1 ≤ M ≤ 100
- 1 ≤ A_i < B_i ≤ N
- 1 ≤ K ≤ 16
- 1 ≤ C_i < D_i ≤ N
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 \vdots A_M B_M K C_1 D_1 \vdots C_K D_K
输出
打印答案。
示例输入 1
4 4 1 2 1 3 2 4 3 4 3 1 2 1 3 2 3
示例输出 1
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
示例输出 2
4
例如,如果人们 1, 2, 3, 4 把他们的球放在盘子上 3, 1, 2, 4分别满足所有条件。
示例输入 3
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
示例输出 3
9