        
        
/*/ Author : Abhishek Chauhan /*/

#include<bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std;

// a+b = a^b + 2*(a&b)
// According to Fermat's little theorem, (a^b)%mod = ((a^(b%(mod - 1)))%mod) if mod is a prime number and not the other way round.
// whenever using a comparator return true only if a<b
// make it forward first if it doesnt work do the reverse 
// vector a = ax + ay b = bx + by then dot porduct is |a||b|cos@ //and also for eas you can use (ax*bx)+(ay*by);

#define rep(i,n)             for(int i=0;i<n;i++)
#define int                  long long
#define pb                   push_back
#define mp                   make_pair
#define all(x)               x.begin(),x.end()
#define mod                  1000000007
#define bpop(x)              __builtin_popcountll((x))
#define fastio               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl                 '\n'

template<class T> 
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

template<class T>
T power(T x, T y){T res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
template<class T>
T powermod(T x, T y, T p){T res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}

const int N = 20;
vector<int>g[N];
int vis[N],col[N];
vector<int>order;
void get(int node){
  vis[node] = 1;
  order.pb(node);
  for(auto x:g[node]){
    if(vis[x]==0){
      get(x);
    }
  }
}

int recur(int i){
  if(i>=order.size()){
    return 1;
  }
  int res = 0;
  vis[order[i]] = 1;
  vector<int>can(4,1);
  for(auto x:g[order[i]]){
    if(col[x]!=0){
      can[col[x]] = 0;
    }
  }
  for(int c=1;c<4;c++){
    if(can[c]){
      col[order[i]] = c;
      res+=recur(i+1);
      col[order[i]] = 0;
    }
  }
  return res;
}

void snow(){

   int n,m;
   cin>>n>>m;
   for(int i=0;i<n;i++){
    vis[i] = 0;
    col[i] = 0;
   }
   for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;a--;b--;
    g[a].pb(b);
    g[b].pb(a);
   }
   int ans = 1;
   for(int i=0;i<n;i++){
    if(!vis[i]){
     order.clear();
     get(i);
     col[order[0]] = 1;
     vis[order[0]] = 1;
     if(order.size()==1){
      ans = ans*3;
     }
     else{
      ans=ans*3*recur(1);
     }
    }
   }
   cout<<ans<<endl;
}


int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    fastio;
    int _;
    _=1;
    for(int i=1;i<=_;i++){
     // cout<<"Case #"<<i<<": ";
        snow();
    }
    return 0;
}





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

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define yes(x) ((x) ? "yes" : "no")
#define Yes(x) ((x) ? "Yes" : "No")

using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using f64 = double_t;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;

void solve() {
    i64 N, M;
    cin >> N >> M;
    vector<p64> conds(M);
    for (auto& [ A, B ] : conds) cin >> A >> B;

    i64 K;
    cin >> K;
    vector<p64> poss(K);
    for (auto& [ C, D ] : poss) cin >> C >> D;

    bitset<128> bs;
    i64 ans = 0;
    for (i64 i = 0; i < (1 << K); i++) {
        i64 can = 0;
        for (i64 j = 0; j < K; j++) {
            auto& [ C, D ] = poss[j];
            bs[(i >> j) & 1 ? C : D] = 1;
        }
        for (i64 j = 0; j < M; j++) {
            auto& [ A, B ] = conds[j];
            can += bs[A] && bs[B];
        }
        ans = max(ans, can);
        bs.reset();
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}
