#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
const int nx=3e5+100;
int ds[nx], dss[nx], c=INT_MAX, cs=INT_MAX, ans, n, p, v[nx], vs[nx];
bool vs1[2*nx], vs2[2*nx];
vector<int> d[2*nx];
void dfs(int u, int s)
{
if (vs1[u]) return;
vs1[u]=1; ds[u]=s;
for (auto v:d[u])
{
if (v==p) c=s+1;
else dfs(v, s+1);
}
}
void dfs2(int u, int s)
{
if (vs2[u]) return;
vs2[u]=1; dss[u]=s;
for (auto v:d[u])
{
if (v==p+n) cs=s+1;
else dfs2(v, s+1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for (int i=0; i<N; i++) ds[i]=dss[i]=INT_MAX, vs[i]=v[i]=-1;
n=N; p=P;
for (int i=0; i<M; i++)
{
if (v[R[i][0]]==-1) v[R[i][0]]=R[i][1];
else if (vs[R[i][0]]==-1) vs[R[i][0]]=R[i][1];
if (v[R[i][1]]==-1) v[R[i][1]]=R[i][0];
else if (vs[R[i][1]]==-1) vs[R[i][1]]=R[i][0];
}
for (int i=0; i<N; i++) if (vs[i]==-1) vs[i]=v[i];
for (int i=0; i<N; i++)
{
if (v[v[i]]==i) d[v[i]+n].push_back(i);
else d[v[i]].push_back(i);
if (v[vs[i]]==i) d[vs[i]+n].push_back(i+n);
else d[vs[i]].push_back(i+n);
}
dfs(p, 0);
dfs2(p+n, 0);
for (int i=0; i<Q; i++)
{
int cnt(0);
for (int j=0; j<n; j++)
{
if (((G[i]-ds[j])%c==0&&ds[j]<=G[i])||((G[i]-dss[j])%cs==0&&dss[j]<=G[i])) cnt++;
}
answer(cnt);
}
}
