У нас є \(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\) (\(2 \le N \le 100\), \(1 \le M \le 100\))

Наступні  \(M\) рядків містять цілі числа \(A_i, B_i\) (\(1 \le A_i < B_i \le N\))

Далі рядок містить ціле число \(K\) (\(1 \le K \le 16\))

Наступні  \(K\) рядків містять цілі числа \(C_i, D_i\) (\(1 \le C_i < D_i \le N\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану кількість.

Примітка

До прикладу 1:

Наприклад, якщо люди 1, 2, 3 кладуть свої кульки на блюда 1, 3, 2 відповідно, умови 1 і 2 будуть задоволені.

Приклад вхідних даних

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

Приклад вихідних даних

9