// ~~ icebear & at~~
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5000 + 5;
int numNode, numEdge, numQuery;
vector<int> G[N];
int dist[N][N], ways[N][N];
bool computed[N];
queue<int> Q;
int a[N], b[N];
void BFS(int x) {
memset(dist[x], 0x3f, sizeof dist[x]);
dist[x][x] = 0;
ways[x][x] = 1;
Q.push(x);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for (int v : G[u])
if (dist[x][v] > dist[x][u] + 1) {
dist[x][v] = dist[x][u] + 1;
ways[x][v] = ways[x][u];
Q.push(v);
} else if (dist[x][v] == dist[x][u] + 1)
ways[x][v] += ways[x][u];
}
}
bool isLarger(array<int, 3> &x, array<int, 3> &y) {
return 1ll * x[0] * y[1] > 1ll * x[1] * y[0];
}
signed main(){
// freopen("TRAINCENTRE.inp", "r", stdin);
// freopen("TRAINCENTRE.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> numNode >> numEdge;
for(int i = 0; i < numEdge; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
cin >> numQuery;
for(int i = 0; i < numQuery; i++) {
cin >> a[i] >> b[i];
if (!computed[a[i]]) {
BFS(a[i]);
computed[a[i]] = true;
}
if (!computed[b[i]]) {
BFS(b[i]);
computed[b[i]] = true;
}
}
array<int, 3> ans = {0, 1, 0};
for(int w = 0; w < numNode; w++) {
int fixedPath = 0, totalPath = 0;
for(int i = 0; i < numQuery; i++) {
if (dist[a[i]][w] + dist[b[i]][w] == dist[a[i]][b[i]])
fixedPath += ways[a[i]][w] * ways[b[i]][w];
totalPath += ways[a[i]][b[i]];
}
int g = __gcd(fixedPath, totalPath);
array<int, 3> tmp = {fixedPath / g, totalPath / g, w};
if (isLarger(tmp, ans)) ans = tmp;
}
cout << ans[2];
return 0;
}
