#include "garden.h"
#include "gardenlib.h"
#include<vector>
#include<cstdio>
constexpr int maxn = 5e5+10;
std::vector<int> g[maxn]; // functional graph reversed
int f[maxn], s[maxn], dist[maxn], ans[maxn], n, lim, p, sz;
bool dirty[maxn], mark[maxn];
void dfs(int u, int d) {
if(u < lim) ++dist[d];
for(int v : g[u])
if(v != p) dfs(v, d+1);
}
void dfs2(int u) {
mark[u] = 1; ++sz;
if(f[u] == p) return;
if(mark[f[u]]) return (void)(sz = 0);
dfs2(f[u]);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N; lim = N; p = P;
for(int i = 0; i < 3*N; i++)
f[i] = s[i] = -1;
for(int i = 0; i < M; i++) {
int a = R[i][0], b = R[i][1];
if(f[a] == -1) f[a] = b;
else if(s[a] == -1) s[a] = b;
if(f[b] == -1) f[b] = a;
else if(s[b] == -1) s[b] = a;
}
for(int a = 0; a < N; a++)
if(f[f[a]] == a) dirty[a] = 1;
for(int a = 0; a < N; a++) {
if(!dirty[a]) continue;
if(s[f[a]] != -1)
f[n] = s[f[a]], f[a] = n++;
else {
if(s[a] == -1) continue;
f[n] = n+1; f[n+1] = s[a];
f[a] = n; n += 2;
}
}
for(int i = 0; i < n; i++)
g[f[i]].push_back(i);
// for(int i = 0; i < n; i++)
// printf("%d %d\n", i, f[i]);
dfs(P, 0);
dfs2(P);
// printf("%d\n", sz);
for(int i = 0; i < sz; i++)
for(int j = i; j < n; j += sz)
ans[i] += dist[j];
for(int i = 0; i < Q; i++) {
int sub = 0;
for(int j = G[i]+sz; sz && j < n; j += sz)
sub += dist[j];
answer(ans[G[i]%sz] - sub);
}
}
