#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 998244353

#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 3e5 + 1;
ll dp[N][30], fac[N]; 
ll dp2[N];
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
 
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

ll modi(ll a, ll m)
{
    return power(a, m - 2, m);
 
}

ll nCr(ll n, ll r, ll p)
{
 
    if (r == 0)
        return 1;
    if(r > n){
        return 0;
    }
    return (fac[n] * modi(fac[r], p) % p *
        modi(fac[n - r], p) % p) % p;
}
vector<ll> adj[N];
ll f(ll idx, ll len){
    ll res = 0;
    if(len == 1){
        return dp[idx][len] = 1;
    }
    if((int)adj[idx].size() == 0){
        return dp[idx][len] = 0;
    }
    if(dp[idx][len] != -1){
        return dp[idx][len];
    }
    for(auto u : adj[idx]){
        res += f(u, len - 1);
        res %= MOD;
    }
    return dp[idx][len] = res;
}
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    memset(dp, -1, sizeof(dp));
    //cin >> T;
    fac[0] = 1;
    for(i = 1; i < N; i++){
        fac[i] = i * fac[i - 1];
        fac[i] %= MOD;
    }
    while (T--) {
        ll n, m;
        cin >> n >> m;
        for(i = 1; i <= m; i++){
            for(j = 2 * i; j <= m; j += i){
                adj[i].pb(j);
                //cout << i << " $$ " << j << endl;
            }
        }
        ll ans = 0;
        for(j = 0; j <= n - 1; j++){
            dp2[j] = nCr(n - 1, j, MOD);
        }
        for(i = 1; i <= m; i++){
            for(j = 1; j <= 21; j++){
                ll mul = dp2[j - 1];
                //cout << n - 1 << " ## " << j - 1 << endl;
                ll x = f(i, j);
                ans += mul * x;
                assert(ans >= 0);
                //cout << mul << " " << x << endl;
                if(x != 0)
                assert(INF / x >= mul);
                //cout << mul << " " << f(i, j) << endl;
                //cout << f(i, j) << " ";
                ans %= MOD;
            }
            //cout << endl;
        }
        //cout << dp[m][1] << endl;
        cout << ans << endl;
    }
    return 0;
}
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using PQ = priority_queue<T>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007; // 998244353;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const ld PI = acos((ld)-1);
constexpr ll dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
inline void Yes() { cout << "Yes" << ENDL; }
inline void No() { cout << "No" << ENDL; }
inline void YES() { cout << "YES" << ENDL; }
inline void NO() { cout << "NO" << ENDL; }

template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template <typename T>
vector<T> finddivisor(T x) {  //整数xの約数(xを含む)
  vector<T> divisor;
  for(T i = 1; (i * i) <= x; i++) {
    if(x % i == 0) {
      divisor.push_back(i);
      if(i * i != x) { divisor.push_back(x / i);}
    }
  }
  sort(divisor.begin(), divisor.end());
  return divisor;
}

template <typename T> V<T> prefix_sum(const V<T>& v) {
  int n = v.size();
  V<T> ret(n + 1);
  rep(i, 0, n) ret[i + 1] = ret[i] + v[i];
  return ret;
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(auto&& x: vec) is >> x;
  return is;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
  return os<<"{"<<p.fs<<","<<p.sc<<"}";
}

template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
  os<<"{";
  for(auto e:v)os<<e<<",";
  return os<<"}";
}

template<typename ...Args>
void debug(Args&... args){
  for(auto const& x:{args...}){
    cerr<<x<<' ';
  }
  cerr<<ENDL;
}



signed main(){
  cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n,m;cin>>n>>m;

  V<ll> a(m),b(m);
  rep(i,0,m){
    cin>>a[i]>>b[i];
    a[i]--;
    b[i]--;
  }

  ll k;cin>>k;
  V<ll> c(k),d(k);
  rep(i,0,k){
    cin>>c[i]>>d[i];
    c[i]--;
    d[i]--;
  }

  ll ans=0;
  rep(bit,0,1<<k){
    V<bool> aru(n,false);
    rep(i,0,k){
      if(bit & (1<<i))aru[c[i]]=true;
      else aru[d[i]]=true;
    }

    ll tmp=0;
    rep(i,0,m){
      if(aru[a[i]] && aru[b[i]])tmp++;
    }
    chmax(ans,tmp);
  }
  cout<<ans<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?
//any other simpler approach?
//list all conditions, try mathematical and graphic observation