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

#ifdef LOCAL
    #define D(a) cerr << #a << " = " << a << endl
#else 
    #define D(a) 8 
#endif
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define all(a) (a).begin(),(a).end()
#define dforn(i,n) dforsn(i,0,n)
#define forn(i,n) forsn(i,0,n)
#define si(a) int((a).size())
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first
#define endl '\n'
using pii = pair<int,int>;
using vi = vector<int>;
using ll = long long;

int n, m, k, ans;
vector<pii> c, o;
vi b;

void f(int l = 0) {
    if (l == k) {
        int cur = 0;
        for (auto [x, y] : c) if (b[x] && b[y]) cur++;
        ans = max(ans, cur);
        return;
    }
    auto [x, y] = o[l];
    b[x]++, f(l + 1), b[x]--;
    b[y]++, f(l + 1), b[y]--;
}

int main() {
	fastio;
	
    cin >> n >> m;
    b.resize(n), c.resize(m);
    for (auto &[x, y] : c) cin >> x >> y, x--, y--;
    cin >> k;
    o.resize(k);
    for (auto &[x, y] : o) cin >> x >> y, x--, y--;
    f();
    cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll mod = 998244353;
ll qp(ll a,ll b = mod - 2)
  {
  	ll ret = 1;
  	while (b)
  	  {
  	  	if (b & 1)
  	  	  ret = ret * a % mod;
		b >>= 1;
		a = a * a % mod;
		}
	return ret;
  }
ll js[400000 + 110];
ll ijs[400000 + 110];
ll d[400000 + 110];
void show(ll n,ll m)
  {
  	static vector<ll> v;
  	if (n == 0)
  	  {
  	  	
  	  	for (ll i = 1;i < v.size();i++)
  	  	  if (v[i - 1] > v[i] or v[i] % v[i - 1] != 0)
  	  	    return;
		static ll cnt = 0;
  	  	cout << ++cnt << " : ";
  	  	for (auto it : v)
  	  	  cout << it << " ";cout << endl;
  	  	return;
		}
	for (ll i = 1;i <= m;i++)
	  {
	  	v.push_back(i);
	  	show(n - 1,m);
	  	v.pop_back();
	  }
  }
ll c(ll n,ll m)
  {
  	if (n < m)
  	  return 0;
  	ll ret = js[n] * ijs[m] % mod * ijs[n - m] % mod;
  	return ret;
  }
map<ll,ll> tong[400000 + 110];
int main()
  {
  	static bool vis[400000 + 110];
  	for (ll i = 2;i <= 400000;i++)
  	  if (vis[i] == 0){
  	  	for (ll k = i;k <= 400000;k += i)
  	  	  {
  	  	    vis[k] = 1;
  	  	    ll now = k;
			while (now % i == 0)
			  tong[k][i]++,
			  now /= i; 
			  }
  	  	  
		}
  	js[0] = 1;
  	for (ll i = 1;i <= 400000;i++)
  	  js[i] = js[i - 1] * i % mod;
  	ijs[400000] = qp(js[400000]);
  	for (ll i = 400000;i >= 1;i--)
  	  ijs[i - 1] = ijs[i] * i % mod;
    for (ll i = 1;i <= 400000;i++)
      for (ll k = i;k <= 400000;k += i)
        d[k]++;
    ll n,m;
    cin >> n >> m;
    ll ret = 0;
    for (ll i = 1;i <= m;i++)
      {
      	ll t = 1;
      	for (auto it : tong[i])
      	  //cout << "+ " << i << " " << it.first << " " << it.second << endl,
      	  t *= c(n + it.second - 1,it.second),
		  t %= mod;
      	///cout << endl;
      	ret += t % mod;
      	ret %= mod;
	  }
	cout << (ret % mod + mod) % mod;
  	return 0;
   } 

