#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>ngp;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
vector<vector<int>>pr(N,vector<int>(2,-1)),ngp(N*2);
int u,v,D1,D2,ans;
vector<bool>cy(N*2);
vector<int>graph(N*2,-1),d1(N*2,-1),d2(N*2,-1);
for(int i=0;i<M;++i){
u=R[i][0];v=R[i][1];
if(pr[u][0]==-1)pr[u][0]=v;
else if(pr[u][1]==-1)pr[u][1]=v;
if(pr[v][0]==-1)pr[v][0]=u;
else if(pr[v][1]==-1)pr[v][1]=u;
}
for(int i=0;i<N;++i){
u=pr[i][0];
graph[i*2]=u*2+(pr[u][0]==i and pr[u][1]!=-1);
u=pr[i][1];
if(u==-1)continue;
graph[i*2+1]=u*2+(pr[u][0]==i and pr[u][1]!=-1);
}
for(int i=0;i<N*2;++i){
if(graph[i]==-1)continue;
ngp[graph[i]].push_back(i);
}
auto cycle=[&](int u)->int{
if(graph[u]==-1)return 0;
vector<bool>vis(N*2),vs(N*2);
int cnt=0;
while(!vis[u]){
vis[u]=1;
u=graph[u];
}
while(!vs[u]){
vs[u]=1;
cy[u]=1;
u=graph[u];
cnt++;
}
return cnt;
};
queue<int>q;
q.push(P*2);
d1[P*2]=d2[P*2+1]=0;
while(!q.empty()){
u=q.front();
q.pop();
for(auto&i:ngp[u])if(d1[i]==-1){
d1[i]=d1[u]+1;
q.push(i);
}
}
q.push(P*2+1);
while(!q.empty()){
u=q.front();
q.pop();
for(auto&i:ngp[u])if(d2[i]==-1){
d2[i]=d2[u]+1;
q.push(i);
}
}
D1=cycle(P*2);
D2=cycle(P*2+1);
P*=2;
for(int j=0;j<Q;++j){
ans=0;
for(int i=0;i<N;++i){
if(cy[P])ans+=(d1[i*2]!=-1 and (G[j]-d1[i*2])%D1==0);
else ans+=(d1[i*2]==G[j]);
if(graph[P+1]!=-1){
if(cy[P+1])ans+=(d2[i*2]!=-1 and (G[j]-d2[i*2])%D2==0);
else ans+=(d2[i*2]==G[j]);
}
}
answer(ans);
}
}
