#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;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgdmVjdG9yPCB2ZWN0b3I8aW50PiA+IEdyYXBoOwp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgbGw7CgpHcmFwaCBnaW5wdXQoaW50IG4sIGludCBtKSB7CiAgICBHcmFwaCBHKG4pOwogICAgZm9yKGludCBpPTA7IGk8bTsgaSsrKSB7CiAgICAgICAgaW50IHMsIHQ7IGNpbiA+PiBzID4+IHQ7CiAgICAgICAgcy0tOyB0LS07CiAgICAgICAgR1tzXS5wdXNoX2JhY2sodCk7CiAgICAgICAgR1t0XS5wdXNoX2JhY2socyk7CiAgICB9CiAgICByZXR1cm4gRzsKfQoKdmVjdG9yPEdyYXBoPiBGb3Jlc3QyVHJlZXMoR3JhcGggJkcpIHsKICAgIGludCBuID0gKGludClHLnNpemUoKTsKICAgIHZlY3RvcjxpbnQ+IHZ0eGlkKG4sIC0xKTsKCiAgICB2ZWN0b3I8R3JhcGg+IHJldDsKICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykgewogICAgICAgIGlmKHZ0eGlkW2ldID49IDApIGNvbnRpbnVlOwogICAgICAgIEdyYXBoIFRyZWUoMSk7CiAgICAgICAgaW50IGN1ciA9IDA7CiAgICAgICAgdnR4aWRbaV0gPSBjdXIrKzsKCiAgICAgICAgcXVldWU8aW50PiBxOyBxLnB1c2goaSk7CiAgICAgICAgd2hpbGUoIXEuZW1wdHkoKSkgewogICAgICAgICAgICBpbnQgayA9IHEuZnJvbnQoKTsgcS5wb3AoKTsKICAgICAgICAgICAgZm9yKHNpemVfdCB4PTA7IHg8R1trXS5zaXplKCk7IHgrKykgewogICAgICAgICAgICAgICAgaW50IHRvID0gR1trXVt4XTsKICAgICAgICAgICAgICAgIGlmKHZ0eGlkW3RvXSA+PSAwKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIHZ0eGlkW3RvXSA9IGN1cisrOwogICAgICAgICAgICAgICAgVHJlZS5wdXNoX2JhY2sodmVjdG9yPGludD4oKSk7CiAgICAgICAgICAgICAgICBUcmVlWyB2dHhpZFtrIF0gXS5wdXNoX2JhY2soIHZ0eGlkW3RvXSApOwogICAgICAgICAgICAgICAgVHJlZVsgdnR4aWRbdG9dIF0ucHVzaF9iYWNrKCB2dHhpZFtrIF0gKTsKICAgICAgICAgICAgICAgIHEucHVzaCh0byk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0LnB1c2hfYmFjayhUcmVlKTsKICAgIH0KICAgIHJldHVybiByZXQ7Cn0KCnZvaWQgZGZzKGludCBwLCBHcmFwaCAmRywgdmVjdG9yPGludD4gJmRpc3QpIHsKICAgIGlmKGRpc3RbcF0gPT0gLTEpIGRpc3RbcF0gPSAwOwogICAgaW50IGN1ciA9IGRpc3RbcF07CiAgICBmb3Ioc2l6ZV90IGk9MDsgaTxHW3BdLnNpemUoKTsgaSsrKSB7CiAgICAgICAgaW50IHRvID0gR1twXVtpXTsKICAgICAgICBpZihkaXN0W3RvXSAhPSAtMSkgY29udGludWU7CiAgICAgICAgZGlzdFt0b10gPSBjdXIgKyAxOwogICAgICAgIGRmcyh0bywgRywgZGlzdCk7CiAgICB9Cn0KCnZlY3RvcjxpbnQ+IGdldENlbnRlcnMoR3JhcGggJkcpIHsKICAgIGludCBuID0gKGludClHLnNpemUoKTsKICAgIHZlY3RvcjxpbnQ+IGQwKG4sIC0xKSwgZDEobiwgLTEpLCBkMihuLCAtMSk7CiAgICBkZnMoMCwgRywgZDApOwogICAgaW50IHAxID0gbWF4X2VsZW1lbnQoZDAuYmVnaW4oKSwgZDAuZW5kKCkpIC0gZDAuYmVnaW4oKTsKICAgIGRmcyhwMSwgRywgZDEpOwogICAgaW50IHAyID0gbWF4X2VsZW1lbnQoZDEuYmVnaW4oKSwgZDEuZW5kKCkpIC0gZDEuYmVnaW4oKTsKICAgIGRmcyhwMiwgRywgZDIpOwoKICAgIHZlY3RvcjxpbnQ+IHJldDsKICAgIGludCBkaWFtZXRlciA9IGQyW3AxXTsKICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykgewogICAgICAgIGJvb2wgYjEgPSAoZDFbaV0gKyBkMltpXSA9PSBkaWFtZXRlcik7CiAgICAgICAgYm9vbCBiMiA9IChkMVtpXSA9PSBkaWFtZXRlciAvIDIgfHwgZDJbaV0gPT0gZGlhbWV0ZXIgLyAyKTsKICAgICAgICBpZihiMSAmJiBiMikgcmV0LnB1c2hfYmFjayhpKTsKICAgIH0KICAgIHJldHVybiByZXQ7Cn0KCm1hcDxzdHJpbmcsIGxsPiBIQVNITUFQOwpsbCBjbnRQYXR0ZXJuLCBUcmVlSGFzaDsKCmxsIGdldEhhc2goR3JhcGggJkcsIGludCBwb2ludCwgaW50IHBhcmVudCA9IC0xKSB7CiAgICAvLyBsZWFmCiAgICBpZihHW3BvaW50XS5zaXplKCkgPT0gMSAmJiBwYXJlbnQgIT0gLTEpCiAgICAgICAgcmV0dXJuIEhBU0hNQVBbIjAiXSA9IDE7CgogICAgdmVjdG9yPHN0cmluZz4gcmVjOwogICAgZm9yKHNpemVfdCBpPTA7IGk8R1twb2ludF0uc2l6ZSgpOyBpKyspIHsKICAgICAgICBpbnQgdG8gPSBHW3BvaW50XVtpXTsKICAgICAgICBpZih0byA9PSBwYXJlbnQpIGNvbnRpbnVlOwogICAgICAgIGxsIHRlbXAgPSBnZXRIYXNoKEcsIHRvLCBwb2ludCk7CiAgICAgICAgcmVjLnB1c2hfYmFjayh0b19zdHJpbmcodGVtcCkpOwogICAgfQogICAgc29ydChyZWMuYmVnaW4oKSwgcmVjLmVuZCgpKTsKICAgIHN0cmluZyBwYXQgPSAiIjsKICAgIGZvcihzaXplX3QgaT0wOyBpPHJlYy5zaXplKCk7IGkrKykgcGF0ICs9IHJlY1tpXTsKICAgIGlmKCFIQVNITUFQLmNvdW50KHBhdCkpIEhBU0hNQVBbcGF0XSA9ICsrY250UGF0dGVybjsKICAgIHJldHVybiBIQVNITUFQW3BhdF07Cn0KCmludCBtYWluKCkgewogICAgY250UGF0dGVybiA9IDE7CiAgICBpbnQgczEsIHMyOwogICAgaW50IG4xLCBtMTsgY2luID4+IG4xID4+IG0xOwogICAgR3JhcGggRm9yZXN0ID0gZ2lucHV0KG4xLCBtMSk7CiAgICB2ZWN0b3I8R3JhcGg+IFRyZWVzID0gRm9yZXN0MlRyZWVzKEZvcmVzdCk7CgogICAgaW50IG4yOyBjaW4gPj4gbjI7CiAgICBHcmFwaCBQYXR0ZXJuID0gZ2lucHV0KG4yLCBuMi0xKTsKICAgIHZlY3RvcjxpbnQ+IHBhdENlbnRlcnMgPSBnZXRDZW50ZXJzKFBhdHRlcm4pOwogICAgczEgPSAoaW50KXBhdENlbnRlcnMuc2l6ZSgpOwogICAgdmVjdG9yPGxsPiBwYXRIYXNoZXM7CiAgICBmb3IoaW50IGk9MDsgaTxzMTsgaSsrKQogICAgICAgIHBhdEhhc2hlcy5wdXNoX2JhY2soIGdldEhhc2goUGF0dGVybiwgcGF0Q2VudGVyc1tpXSkgKTsKCiAgICBpbnQgYW5zID0gMDsKICAgIGZvcihzaXplX3QgaT0wOyBpPFRyZWVzLnNpemUoKTsgaSsrKSB7CiAgICAgICAgaWYoVHJlZXNbaV0uc2l6ZSgpICE9IFBhdHRlcm4uc2l6ZSgpKSBjb250aW51ZTsKICAgICAgICB2ZWN0b3I8aW50PiB0cmVlQ2VudGVycyA9IGdldENlbnRlcnMoVHJlZXNbaV0pOwogICAgICAgIHMyID0gKGludCl0cmVlQ2VudGVycy5zaXplKCk7CiAgICAgICAgaWYoczEgIT0gczIpIGNvbnRpbnVlOwogICAgICAgIGZvcihpbnQgaj0wOyBqPHMyOyBqKyspIHsKICAgICAgICAgICAgbGwgdHJlZUhhc2ggPSBnZXRIYXNoKFRyZWVzW2ldLCB0cmVlQ2VudGVyc1tqXSk7CiAgICAgICAgICAgIGlmKHRyZWVIYXNoID09IHBhdEhhc2hlc1swXSkgewogICAgICAgICAgICAgICAgYW5zKys7IGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgY291dCA8PCBhbnMgPDwgZW5kbDsKICAgIHJldHVybiAwOwp9