#include"garden.h"
#include"gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=15e4+5;
const int INF=2e9;
pair<int,int> nex[MAXN][2];
vector< pair<int,int> > ds[MAXN],vi[MAXN][2];
int dp[MAXN][2],ans[MAXN];
queue< pair<int,int> > pq;
void count_routes(int N,int M,int P,int R[][2],int Q,int G[])
{
for(int i=0;i<M;i++) ds[R[i][0]].push_back({i,R[i][1]}),ds[R[i][1]].push_back({i,R[i][0]});
for(int i=0;i<N;i++) sort(ds[i].begin(),ds[i].end());
for(int i=0;i<N;i++) for(int j=0;j<2&&j<ds[i].size();j++)
{
int p=ds[i][j].second;
if(ds[p].size()==1||ds[p][0].first!=ds[i][j].first) nex[i][j]={p,0};
else nex[i][j]={p,1};
vi[nex[i][j].first][nex[i][j].second].push_back({i,j});
}
for(int t=0;t<2&&t<ds[P].size();t++)
{
for(int i=0;i<N;i++) for(int j=0;j<2;j++) dp[i][j]=INF;
dp[P][t]=0,pq.push({P,t});
while(!pq.empty())
{
int a=pq.front().first,b=pq.front().second;
pq.pop();
for(auto v:vi[a][b]) if(dp[v.first][v.second]==INF) dp[v.first][v.second]=dp[a][b]+1,pq.push(v);
}
int c=1,x=P,y=t,px,py;
while(((px=nex[x][y].first)!=P)+((py=nex[x][y].second)!=t))
{
x=px,y=py,c++;
if(c>N*2) break;
}
if(c>N*2) c=INF;
for(int i=0;i<Q;i++) for(int j=0;j<N;j++) if(dp[j][0]<=G[i]&&(G[i]-dp[j][0])%c==0) ans[i]++;
}
for(int i=0;i<Q;i++) answer(ans[i]);
}
