Contest Duration: - (local time) (100 minutes) Back to Home
C - Bowls and Dishes /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1, 2, \dots, N の番号がついた N 個の皿と、1, 2, \dots, M の番号がついた M 個の条件があります。

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

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

2

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

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

### 出力例 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

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.

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.

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