#include <bits/stdc++.h>
using namespace std;
typedef vector< vector<int> > Graph;
typedef long long int ll;

Graph ginput(int n, int m) {
    Graph G(n);
    for(int i=0; i<m; i++) {
        int s, t; cin >> s >> t;
        s--; t--;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    return G;
}

vector<Graph> Forest2Trees(Graph &G) {
    int n = (int)G.size();
    vector<int> vtxid(n, -1);

    vector<Graph> ret;
    for(int i=0; i<n; i++) {
        if(vtxid[i] >= 0) continue;
        Graph Tree(1);
        int cur = 0;
        vtxid[i] = cur++;

        queue<int> q; q.push(i);
        while(!q.empty()) {
            int k = q.front(); q.pop();
            for(size_t x=0; x<G[k].size(); x++) {
                int to = G[k][x];
                if(vtxid[to] >= 0) continue;
                vtxid[to] = cur++;
                Tree.push_back(vector<int>());
                Tree[ vtxid[k ] ].push_back( vtxid[to] );
                Tree[ vtxid[to] ].push_back( vtxid[k ] );
                q.push(to);
            }
        }
        ret.push_back(Tree);
    }
    return ret;
}

void dfs(int p, Graph &G, vector<int> &dist) {
    if(dist[p] == -1) dist[p] = 0;
    int cur = dist[p];
    for(size_t i=0; i<G[p].size(); i++) {
        int to = G[p][i];
        if(dist[to] != -1) continue;
        dist[to] = cur + 1;
        dfs(to, G, dist);
    }
}

vector<int> getCenters(Graph &G) {
    int n = (int)G.size();
    vector<int> d0(n, -1), d1(n, -1), d2(n, -1);
    dfs(0, G, d0);
    int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
    dfs(p1, G, d1);
    int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
    dfs(p2, G, d2);

    vector<int> ret;
    int diameter = d2[p1];
    for(int i=0; i<n; i++) {
        bool b1 = (d1[i] + d2[i] == diameter);
        bool b2 = (d1[i] == diameter / 2 || d2[i] == diameter / 2);
        if(b1 && b2) ret.push_back(i);
    }
    return ret;
}

map<string, ll> HASHMAP;
ll cntPattern, TreeHash;

ll getHash(Graph &G, int point, int parent = -1) {
    // leaf
    if(G[point].size() == 1 && parent != -1)
        return HASHMAP["0"] = 1;

    vector<string> rec;
    for(size_t i=0; i<G[point].size(); i++) {
        int to = G[point][i];
        if(to == parent) continue;
        ll temp = getHash(G, to, point);
        rec.push_back(to_string(temp));
    }
    sort(rec.begin(), rec.end());
    string pat = "";
    for(size_t i=0; i<rec.size(); i++) pat += rec[i];
    if(!HASHMAP.count(pat)) HASHMAP[pat] = ++cntPattern;
    return HASHMAP[pat];
}

int main() {
    cntPattern = 1;
    int s1, s2;
    int n1, m1; cin >> n1 >> m1;
    Graph Forest = ginput(n1, m1);
    vector<Graph> Trees = Forest2Trees(Forest);

    int n2; cin >> n2;
    Graph Pattern = ginput(n2, n2-1);
    vector<int> patCenters = getCenters(Pattern);
    s1 = (int)patCenters.size();
    vector<ll> patHashes;
    for(int i=0; i<s1; i++)
        patHashes.push_back( getHash(Pattern, patCenters[i]) );

    int ans = 0;
    for(size_t i=0; i<Trees.size(); i++) {
        if(Trees[i].size() != Pattern.size()) continue;
        vector<int> treeCenters = getCenters(Trees[i]);
        s2 = (int)treeCenters.size();
        if(s1 != s2) continue;
        for(int j=0; j<s2; j++) {
            ll treeHash = getHash(Trees[i], treeCenters[j]);
            if(treeHash == patHashes[0]) {
                ans++; break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 55596