#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
vector< int > edg[700005];
int n;
int nxt[700005];
vector<int> p[700005];
bool vis1[700005], vis2[700005];
int dis1[700005], dis2[700005];
vector<int> ans1[700005], ans2[700005];
vector<int> cycle;
int mod1, mod2;
void rdfs1(int x, int dis) {
if(x<n) ans1[dis%mod1].push_back(dis);
for(int i:p[x]) {
if(vis1[i]) continue;
rdfs1(i, dis+1);
}
}
void rdfs2(int x, int dis) {
if(x<n) ans2[dis%mod2].push_back(dis);
for(int i:p[x]) {
if(vis2[i]) continue;
rdfs2(i, dis+1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
for(int i=0; i<M; i++) {
edg[R[i][0]].push_back(R[i][1]);
edg[R[i][1]].push_back(R[i][0]);
}
for(int i=0; i<2*N; i++) {
int dest;
if(i<N) {
dest = edg[i][0];
}
else {
if(edg[i%N].size()==1) dest = -1;
else dest = edg[i%N][1];
}
if(dest!=-1 && i%N == edg[dest][0] && edg[dest].size()>1) dest+=N;
nxt[i] = dest;
if(dest!=-1) p[dest].push_back(i);
}
int ptr = P;
int tmp = 0;
if(nxt[ptr] != -1) {
while(!vis1[ptr]) {
vis1[ptr] = true;
dis1[ptr] = tmp;
ptr = nxt[ptr];
tmp++;
}
if(ptr != P) { // non-cyclic case
for(int i=0; i<2*N; i++) vis1[i] = false;
vis1[P] = true;
mod1 = 2e9;
rdfs1(P, 0);
} else {
mod1 = tmp;
for(int i=0; i<2*N; i++) {
if(vis1[i]) rdfs1(i, (mod1-dis1[i])%mod1);
}
}
}
ptr = P+n;
tmp = 0;
while(!vis2[ptr]) {
vis2[ptr] = true;
dis2[ptr] = tmp;
ptr = nxt[ptr];
tmp++;
}
if(ptr != P+n) {
for(int i=0; i<2*N; i++) vis2[i] = false;
vis2[P+n] = true;
mod2 = 2e9;
rdfs2(P+n, 0);
} else {
mod2 = tmp;
for(int i=0; i<2*N; i++) {
if(vis2[i]) rdfs2(i, (mod2-dis2[i])%mod2);
}
}
for(int i=0; i<=4*n; i++) {
sort(ans1[i].begin(), ans1[i].end());
sort(ans2[i].begin(), ans2[i].end());
}
for(int i=0; i<Q; i++) {
int g = G[i];
int ans = 0;
if(g%mod1 < 4*n)
ans += upper_bound(ans1[g%mod1].begin(), ans1[g%mod1].end(), g) - ans1[g%mod1].begin();
if(g%mod2 < 4*n)
ans += upper_bound(ans2[g%mod2].begin(), ans2[g%mod2].end(), g) - ans2[g%mod2].begin();
answer(ans);
}
}
