#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
#define pb push_back
const int MX = 450005,L=30;
vector<pair<int,int> > vec[150005];
vector<int> res[MX],queries[MX],dp,anc;
int nxt[MX],d[MX],rf[MX],g[2002],ans[2002],edge[150005][2],r,no,m,Tar;
bitset<MX> vis;
void dfs(int node){
rf[node]=r;
vis[node]=1;
if(node>=(2*m))
dp.pb(node);
for(auto it:res[node])
if(it!=no)d[it]=d[node]+1,dfs(it);
}
void solve(int node){
for(auto it:queries[node]){
assert(sz(anc)>=g[it]);
int final=anc[sz(anc)-g[it]];
ans[it]+=(((final>=m)?edge[final-m][0]:edge[final][1])==Tar);
}
anc.pb(node);
for(auto it:res[node])
if(it!=no)solve(it);
anc.pop_back();
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
m=M,Tar=P;
for (int i = 0; i < Q; ++i)
g[i]=G[i];
for (int i = 0; i < M; ++i)
{
edge[i][0]=R[i][0];
edge[i][1]=R[i][1];
vec[R[i][0]].pb({R[i][1],i});
vec[R[i][1]].pb({R[i][0],M+i});
}
for (int i = 0; i < N; ++i)
{
multiset<pair<int,int> > myset;
for (int j = 0; j < sz(vec[i]); ++j)
{
int val=vec[i][j].se-((vec[i][j].se>=M)?M:0);
myset.insert({val,j});
}
for (int j = 0; j < sz(vec[i]); ++j)
{
int val=vec[i][j].se-((vec[i][j].se>=M)?M:0);
int c=val+((vec[i][j].se>=M)?0:M);
myset.erase(myset.find({val,j}));
if(!sz(myset))nxt[c]=vec[i][j].se;
else nxt[c]=vec[i][myset.begin()->se].se;
myset.insert({val,j});
}
nxt[i+2*M]=vec[i][myset.begin()->se].se;
}
for (int i = 0; i < 2*M+N; ++i)
if(nxt[i]!=-1)res[nxt[i]].pb(i);
for (int i = 0; i < N; ++i)
{
if(vis[i+2*M])continue;
int node=i+2*M,st,p;
while(1){
vis[node]=1;
node=nxt[node];
if(vis[node])break;
}
vector<int> cycle={node};
p=node,st=nxt[node];
while(st!=node){
cycle.pb(st);
no=p,r=sz(cycle)-1,dfs(st);
p=st;
st=nxt[st];
}
no=cycle.back(),r=0,dfs(node);
for(auto it:dp){
for (int j = 0; j < Q; ++j)
{
if(d[it]>G[j])
queries[it].pb(j);
else{
int rm=G[j]-d[it];
int final=cycle[(rf[it]+rm)%sz(cycle)];
assert(final<(2*M));
ans[j]+=(((final>=M)?R[final-M][0]:R[final][1])==P);
}
}
}
for (int j = 0; j < sz(cycle); ++j)
{
no=cycle[(j+sz(cycle)-1)%sz(cycle)];
solve(cycle[j]);
}
dp.clear();
}
for (int i = 0; i < Q; ++i)
answer(ans[i]);
}
