#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll = long long; using ull = unsigned long long; using pll = pair<ll,ll>; const ll INF = 4e18;
void print0() {}
template<typename Head,typename... Tail> void print0(Head head,Tail... tail){cout<<fixed<<setprecision(15)<<head;print0(tail...);}
void print() { print0("\n"); }
template<typename Head,typename... Tail>void print(Head head,Tail... tail){print0(head);if(sizeof...(Tail)>0)print0(" ");print(tail...);}
// clang-format on

int main() {
    ll n, m;
    cin >> n >> m;

    vector<ll> nodes(n);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        nodes[a] |= (1ULL << b);
        nodes[b] |= (1ULL << a);
    }

    vector<ll> dp((1ULL << n), INF);  // INF*2でもオーバーフローしないこと

    // 完全グラフかどうか調査 O(2^n)
    // もうちょい雑にやるなら O(n * 2^n) , O(n^2 * 2^n) とかのほうが楽
    ll msb = 1;
    ll msb_node = 0;
    for (ll i = 1; i < ll(1ULL << n); i++) {
        if ((msb << 1) <= i) {
            msb = msb << 1;
            msb_node++;
        }
        ll rest = msb ^ i;
        if (rest == 0) {
            dp[i] = 1;
        } else if ((nodes[msb_node] & rest) == rest && dp[rest] == 1) {
            dp[i] = 1;
        }
    }

    // j<=i, rest<=i なのでトポロジカル順序にはなっている
    for (ll i = 0; i < ll(1ULL << n); i++) {
        // 部分集合の列挙 (O(3^n) / n=18 -> 3^n≒3.9e8)
        // https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361
        for (ll j = i;; j = (j - 1) & i) {
            ll rest = i ^ j;  // 残り
            dp[i] = min(dp[i], dp[j] + dp[rest]);
            if (!j) break;
        }
    }
    print(dp[(1ULL << n) - 1]);
}

#include <bits/stdc++.h>
#define nput(a) cout << a << endl
#define sput(a) cout << a << ' '
using namespace std;
typedef long long ll;
const int maxn = 110;
int a[maxn], b[maxn];
int c[17], d[17];
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
    }
    int k;
    cin >> k;
    for (ll i = 0; i < k; i++)
        cin >> c[i] >> d[i];
    int ans = 0;
    for (int i = 0; i < (1 << k); i++) {
        int use[102] = {0};
        for (int j = 0; j < k; j++) {
            if ((1 << j) & i)
                use[c[j]] = 1;
            else
                use[d[j]] = 1;
        }
        int cnt = 0;
        for (int j = 0; j < m; j++) {
            if (use[a[j]] && use[b[j]])
                cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(false);
    int t;
    t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}