C - Bowls and Dishes 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

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 のどちらか一方にボールを置きます。
満たされる条件の個数は最大でいくつでしょうか？

制約

  • 入力は全て整数
  • 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 つが満たされます。

入力例 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

Score : 300 points

Problem Statement

We have N dishes numbered 1, 2, \dots, N and M conditions numbered 1, 2, \dots, M.
Condition i is satisfied when both Dish A_i and Dish B_i have (one or more) balls on them.
There are K people numbered 1, 2, \dots, K. Person i will put a ball on Dish C_i or Dish D_i.
At most how many conditions will be satisfied?

Constraints

  • All values in input are integers.
  • 2 ≤ N ≤ 100
  • 1 ≤ M ≤ 100
  • 1 ≤ A_i < B_i ≤ N
  • 1 ≤ K ≤ 16
  • 1 ≤ C_i < D_i ≤ N

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

2

For example, if People 1, 2, 3 put their balls on Dishes 1, 3, 2, respectively, Conditions 1 and 2 will be satisfied.

Sample Input 2

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

Sample Output 2

4

For example, if People 1, 2, 3, 4 put their balls on Dishes 3, 1, 2, 4, respectively, all conditions will be satisfied.

Sample Input 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

Sample Output 3

9