#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
#define MAXN 300009
using namespace std;
int P[MAXN][30];
vector<int>adj[MAXN];
void count_routes(int N, int M, int p, int R[][2], int Q, int G[]){
memset(P,-1,sizeof P);
for(int i=0;i<M;i++){
int x=R[i][0],y=R[i][1];
if(adj[x].size()<2)adj[x].push_back(y);
if(adj[y].size()<2)adj[y].push_back(x);
}
for(int i=0;i<N;i++)
for(int j=0;j<(int)adj[i].size();j++){
int to=adj[i][j];
if(adj[to][0]==i and adj[to].size()>1)
P[i+j*N][0]=to+N;
else
P[i+j*N][0]=to;
}
for(int j=1;j<30;j++)
for(int i=0;i<N*2;i++)
if(~P[i][j-1])
P[i][j]=P[P[i][j-1]][j-1];
for(int i=0;i<Q;i++){
int res=0,nd,K;
for(int j=0;j<N;j++){
nd=j;K=G[i];
for(int k=29;k>=0;k--)
if(K>=(1<<k))
nd=P[nd][k],K-=(1<<k);
res+=(nd==p or nd==p+N);
}
answer(res);
}
}
