#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX =1000000000000000000;
ll mod= 1000000000;
long double pi=3.141592653589793238;
void pls()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
}
ll n,m,k;
vector<pair<ll,ll>> p,temp;
ll recursion(int i,vector<int> &visi){
   if(i==k)
   {
        ll tot=0;
        for(i=0;i<p.size();i++){
            if(visi[p[i].first] && visi[p[i].second])
              tot++;
            
        }
        return tot;
    }

        visi[temp[i].first]+=1;
        ll val=recursion(i+1,visi);
        visi[temp[i].first]-=1;
        visi[temp[i].second]+=1;
        ll val1=recursion(i+1,visi);
        visi[temp[i].second]-=1;
        return max(val,val1);
   

}
void solve()
{   
          cin>>n>>m;
          for(int i=0;i<m;i++){
            ll x,y; cin>>x>>y;
            p.push_back({x,y});
          }
          cin>>k;
          for(int i=0;i<k;i++){
            ll x,y; cin>>x>>y;
            temp.push_back({x,y});
          }
          vector<int> visi(n+1,0);
          cout<<recursion(0,visi)<<endl;
       
}
int main(){pls(); solve(); return 0;}
/*
  Mostly wrong answer form base case or overflow or runtime 
  Debug--> check overflow---> check varible name---> check logic implementation----> check logic

*/










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

int ara[262150],n,two[23],tra[23][23],dp[262150],sz,bits[23],tz;

int on(int val,int pos)
{
    return (val|two[pos]);
}

bool ck(int val,int pos)
{
    return (bool)(val&two[pos]);
}

int off(int val,int pos)
{
    return (val^two[pos]);
}

void subsets(int mask,int idx)
{

    if(idx==n){  ara[mask]=1;  }
    else
    {

        subsets(mask,idx+1);

        int flg=1;

        for(int lp=0;lp<=n-1;lp++)
        {
            if(ck(mask,lp)==true)
            {
                if(tra[idx][lp]==0){ flg=0; break;  }
            }

        }


        if(flg==1)
        {
            int t;  t=on(mask,idx);  subsets(t,idx+1);
        }


    }

}


void work(int mask,int start,int idx)
{

    if(idx==tz)
    {
         int remain;
         if(mask!=0){  remain=start^mask;  dp[start]=min(dp[start],dp[mask]+dp[remain]); }
    }
    else
    {
        work(mask,start,idx+1);

        int q,r,s;  q=bits[idx];

        r=off(mask,q);

        work(r,start,idx+1);

    }

}

int main()
{

    two[0]=1;

    for(int lp=1;lp<=20;lp++)
    {
        two[lp]=two[lp-1]*2;

    }


    int m,i,j,k,a,b,c,fn,mask,x,y,z;

    scanf("%d %d",&n,&m);

    for(i=1;i<=m;i++)
    {

        scanf("%d %d",&a,&b); tra[a-1][b-1]=1;  tra[b-1][a-1]=1;
    }


    subsets(0,0); fn=two[n]-1;


    for(mask=1;mask<=fn;mask++)
    {

        if(ara[mask]==1){  dp[mask]=1;  }
        else
        {

           tz=0;  dp[mask]=99999;

           for(i=0;i<=n-1;i++)
           {
               if(ck(mask,i)==true){  bits[tz]=i;  tz++;  }
           }


           work(mask,mask,0);


        }


    }



    printf("%d\n",dp[fn]);



    return 0;
}
