#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector<int> Gr[150005],cir[300005],nG[300005],ans[2];
int to[300005],in[300005],bln[300005],pl[300005],preans[300005],cnt[300005],ANS[2005];
void dfs1(int u,int d)
{
if(u&1^1) ++preans[d];
for(int i:nG[u])
dfs1(i,d+1);
}
void dfs2(int u,int d,int t)
{
if(u&1^1) ans[t].pb(d);
for(int i:nG[u])
dfs2(i,d+1,t);
}
void doit(int x,int t)
{
if(!bln[x])
dfs1(x,0);
else
{
for(int i=0;i<cir[bln[x]].size();++i)
dfs2(cir[bln[x]][(pl[x]-i+cir[bln[x]].size())%cir[bln[x]].size()],i,t);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int tp=0;
queue<int> q;
for(int i=0;i<M;++i)
Gr[R[i][0]].pb(R[i][1]),Gr[R[i][1]].pb(R[i][0]);
for(int i=0;i<N;++i)
{
if(i==Gr[Gr[i][0]][0])
to[i<<1]=Gr[i][0]<<1|1;
else
to[i<<1]=Gr[i][0]<<1;
if(Gr[i].size()>1)
if(i==Gr[Gr[i][1]][0])
to[i<<1|1]=Gr[i][1]<<1|1;
else
to[i<<1|1]=Gr[i][1]<<1;
else
if(i==Gr[Gr[i][0]][0])
to[i<<1|1]=Gr[i][0]<<1|1;
else
to[i<<1|1]=Gr[i][0]<<1;
++in[to[i<<1]],++in[to[i<<1|1]];
}
for(int i=0;i<2*N;++i)
if(!in[i]) q.push(i);
while(!q.empty())
{
int u=q.front();
q.pop();
if(--in[to[u]]==0) q.push(to[u]);
nG[to[u]].pb(u);
}
for(int i=0;i<2*N;++i)
if(in[i])
{
++tp;
for(int j=i;in[j];j=to[j])
in[j]=0,bln[j]=tp,pl[j]=cir[tp].size(),cir[tp].pb(j);
}
doit(P<<1,0),doit(P<<1|1,1);
sort(ALL(ans[0])),sort(ALL(ans[1]));
vector<pii> query;
for(int i=0;i<Q;++i)
query.pb(MP(G[i],i));
sort(ALL(query));
if(bln[P<<1])
for(int i=0,j=0;i<Q;++i)
{
while(j<ans[0].size()&&ans[0][j]<=query[i].F)
++cnt[ans[0][j]%cir[bln[P<<1]].size()],++j;
ANS[query[i].S]+=cnt[query[i].F%cir[bln[P<<1]].size()];
}
MEM(cnt,0);
if(bln[P<<1|1])
for(int i=0,j=0;i<Q;++i)
{
while(j<ans[1].size()&&ans[1][j]<=query[i].F)
++cnt[ans[1][j]%cir[bln[P<<1|1]].size()],++j;
ANS[query[i].S]+=cnt[query[i].F%cir[bln[P<<1|1]].size()];
}
for(int i=0;i<Q;++i)
if(G[i]<2*N) ANS[i]+=preans[G[i]];
for(int i=0;i<Q;++i)
answer(ANS[i]);
}
