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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int q;
int qs[]={8931919,114514,10101551};
int po[333333];
int mod=1000000007;

int par[333333];
int dist[333333];
bool used[333333];
vint vs;
void dfs(int s,vector<vint>&G){
    vint ord,p,d;
    ord.pb(s);
    p.pb(-1);
    d.pb(0);
    for(int i=0;i<ord.size();i++){
        int v=ord[i];
        for(auto u:G[v]){
            if(u==p[i])continue;
            ord.pb(u);
            p.pb(v);
            d.pb(d[i]+1);
        }
    }

    for(int i=0;i<ord.size();i++){
        par[ord[i]]=p[i];
        dist[ord[i]]=d[i];
        vs.pb(ord[i]);
    }
}

int tmp[333333];

int dfs2(int s,vector<vint>&G){
    vint ord,p,d,sz;
    ord.pb(s);
    p.pb(-1);
    d.pb(0);
    for(int i=0;i<ord.size();i++){
        int v=ord[i];
        for(auto u:G[v]){
            if(u==p[i])continue;
            ord.pb(u);
            p.pb(v);
            d.pb(d[i]+1);
        }
    }

    rep(i,ord.size())tmp[ord[i]]=i;

    vector<int>hs(ord.size());
    sz.resize(ord.size());
    for(int i=ord.size()-1;i>=0;i--){
        int v=ord[i];
        hs[i]=(int)d[i];
        sz[i]=1;
        vector<pint>lis;
        for(auto u:G[v]){
            if(u==p[i])continue;
            lis.pb({hs[tmp[u]],sz[tmp[u]]});
            sz[i]+=sz[tmp[u]];
        }
        sort(all(lis));
        for(auto x:lis)hs[i]=(hs[i]*po[x.se]+x.fi)%mod;
    }

    return hs[0];
}

vector<int> calc(vector<vector<int>>&G,int s){
    vs.clear();
    dfs(s,G);
    int ma=0;
    rep(i,vs.size())if(dist[vs[ma]]<dist[vs[i]])ma=i;

    int v1=vs[ma];
    vs.clear();
    dfs(v1,G);
    ma=0;
    rep(i,vs.size())if(dist[vs[ma]]<dist[vs[i]])ma=i;
    int v2=vs[ma];

    int di=dist[v2];
    int m=v2;
    rep(i,di/2)m=par[m];

    vector<int> ret;
    ret.pb(dfs2(m,G));
    if(di&1){
        m=par[m];
        ret.pb(dfs2(m,G));
    }
    sort(all(ret));
    rep(i,vs.size())used[vs[i]]=true;
    return ret;
}

bool ok[333333][3];

signed main(){
    int N,M;
    scanf("%lld%lld",&N,&M);
    vector<vint>G1(N);
    rep(i,M){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        G1[a].pb(b);G1[b].pb(a);
    }

    int n;
    scanf("%lld",&n);
    vector<vint>G2(n);
    rep(i,n-1){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        G2[a].pb(b);G2[b].pb(a);
    }

    rep(t,3){
        q=qs[t];
        po[0]=1;
        for(int i=1;i<333333;i++)po[i]=po[i-1]*q%mod;
    auto vec=calc(G2,0);
    memset(used,0,sizeof(used));
    for(int i=0;i<N;i++){
        if(used[i])continue;
        auto vec2=calc(G1,i);
        if(vec.size()!=vec2.size())continue;
        bool flag=true;
        rep(j,vec.size()){
            flag&=vec[j]==vec2[j];
        }
        ok[i][t]=flag;
    }
    }


int ans=0;
rep(i,N){
    if(ok[i][0]&&ok[i][1]&&ok[i][2])ans++;
}
cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 51708