← 返回题目列表

AtCoder · abc190_c

C. 碗盘

中文机器翻译题面 查看原题

分数: 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