#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150005;
const int TMAX = 300005;
vector<int> adj[TMAX],radj[TMAX];
int nxt[TMAX];
int indeg[TMAX],sz[TMAX];
int dist0[MAXN],dist1[MAXN];
int cyc0[MAXN],cyc1[MAXN];
bool vis[TMAX];
vector<int> cyc;
void calc(int st, int *dist, int *cycs){
memset(vis,false,sizeof(vis));
queue<int> q, dq, cq;
q.push(st); dq.push(0); cq.push(-1);
dist[st] = 0; cycs[st] = -1; vis[st] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
int cd = dq.front(); dq.pop();
int cc = cq.front(); cq.pop();
cc = max(cc,sz[u]);
if(u%2 == 0){
dist[u/2] = cd;
cycs[u/2] = cc;
}
for(auto v : radj[u]){
if(!vis[v]){
vis[v] = true;
q.push(v);
dq.push(cd+1);
cq.push(cc);
}
}
}
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
memset(dist0,-1,sizeof(dist0)); memset(dist1,-1,sizeof(dist1));
memset(cyc0,-1,sizeof(cyc0)); memset(cyc1,-1,sizeof(cyc1));
memset(sz,-1,sizeof(sz));
for(int i = 0;i<M;++i){
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
for(int i = 0;i<N;++i){
if(!adj[i].size()) continue;
int v = adj[i][0];
if(adj[v][0] != i){
nxt[2*i] = 2*v;
}
else{
nxt[2*i] = 2*v+1;
}
if(adj[i].size() == 1){
nxt[2*i+1] = nxt[2*i];
}
else{
int v2 = adj[i][1];
if(adj[v2][0] != i){
nxt[2*i+1] = 2*v2;
}
else{
nxt[2*i+1] = 2*v2+1;
}
}
//cout << 2*i << " " << nxt[2*i] << " " << 2*i+1 << " " << nxt[2*i+1] << "\n";
}
for(int i = 0;i<2*N;++i){
++indeg[i]; ++indeg[nxt[i]];
}
queue<int> q;
for(int i = 0;i<2*N;++i){
if(indeg[i] == 1) q.push(i);
}
while(!q.empty()){
int u = q.front(); q.pop();
--indeg[u]; --indeg[nxt[u]];
if(indeg[nxt[u]] == 1) q.push(nxt[u]);
}
for(int i = 0;i<2*N;++i){
radj[nxt[i]].push_back(i);
if(indeg[i]){ //cycle
cyc.clear(); int u = i;
while(indeg[u]){
indeg[u] = 0;
//cout << u << " ";
cyc.push_back(u);
u = nxt[u];
}
//cout << "\n";
for(auto x : cyc) sz[x] = cyc.size();
}
}
calc(2*P,dist0,cyc0); calc(2*P+1,dist1,cyc1);
for(int i = 0;i<Q;++i){
int K = G[i], ans = 0;
for(int u = 0;u<N;++u){
if(dist0[u] != -1){
if(cyc0[u] != -1){
if((K-dist0[u])%cyc0[u] == 0 && dist0[u] <= K){
++ans;
continue;
}
}
else{
if(dist0[u] == K){
++ans;
continue;
}
}
}
if(dist1[u] != -1){
if(cyc1[u]!= -1){
if((K-dist1[u])%cyc1[u] == 0 && dist1[u] <= K){
++ans;
continue;
}
}
else{
if(dist1[u] == K){
++ans;
}
}
}
}
answer(ans);
}
}
