いろいろ制約がたくさんですが、$2^K$通りを調べればよく、Kも最大で16なので全探索してしまいます。
2つのうちのどちらかを選び続ける実装で、自分は再帰を使いがちなんですが他にいい方法はあったりするのだろうか。
全部の選択が終わったら満たされる条件の数を計算して最大値を求めています。
言語はC++(GCC 9.2.1)でAtCoderのコードテストで確認しています。

#include <bits/stdc++.h>
using namespace std;

int N, M, K;
vector<int> A(101), B(101), C(16), D(16);

int maxCondition(vector<int> E, int index) {
  if (index == K) {
    int count = 0;
    for (int i = 0; i < M; i++) {
      if (E[A[i]] && E[B[i]]) count++;
    }
    return count;
  }

  int count1, count2;
  E[C[index]]++;
  count1 = maxCondition(E, index+1);
  E[C[index]]--;
  E[D[index]]++;
  count2 = maxCondition(E, index+1);

  return max(count1, count2);
}

int main() {
  cin >> N >> M;
  
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
  }

  cin >> K;

  for (int i = 0; i < K; i++) {
    cin >> C[i] >> D[i];
  }
  
  vector<int> E(101, 0);
  cout << maxCondition(E, 0) << endl;
}