#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define eb emplace_back
const int mxn = 3e5+5;
vi adj[mxn];
int n,q,F[mxn],deg[mxn],vis[mxn],dist[mxn],D[mxn],Cnt[mxn],ans[2002];
struct query{
int k,ind;
query(int kk, int i){
k=kk,ind=i;
}
bool operator < (const query &rhs)const{
return k<rhs.k;
}
};
vector<query>qq;
void add(int a, int b, int ind){
if(vis[a]==ind){
if(vis[b]!=ind||deg[b]==1)F[a]=b;
else F[a]=b+n;
}else if(F[a+n]==-1){
if(vis[b]!=ind||deg[b]==1)F[a+n]=b;
else F[a+n]=b+n;
}
}
void dfs(int u, int d){
dist[u]=d;
for(int v:adj[u]){
if(dist[v]==-1)dfs(v,d+1);
}
}
void run(int st){
for(int i=0; i<=2*n; i++){
dist[i]=-1;
vis[i]=0;
Cnt[i]=0;
}
dfs(st,0);
int cnt = 0;
for(int i=0; i<2*n; i++){
if(dist[i]!=-1){
D[cnt++]=dist[i];
}
}
sort(D,D+cnt);
//calculate cycle size
int c = 0;
int now = st;
while(!vis[now]){
c++;
vis[now]=1;
now = F[now];
}
if(now!=st)c=1000000009;
int ptr = 0;
for(int i=0; i<q; i++){
while(ptr<cnt&&D[ptr]<=qq[i].k){
Cnt[D[ptr]%c]++;
ptr++;
}
int md = qq[i].k%c;
if(md>2*n)continue;
ans[qq[i].ind]+=Cnt[md];
}
return;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n=N,q=Q;
int m=M;
for(int i=0; i<q; i++){
qq.eb(G[i],i);
}
sort(qq.begin(),qq.end());
for(int i=0; i<m; i++){
int u = R[i][0], v = R[i][1];
deg[u]++,deg[v]++;
if(!vis[u])vis[u]=i+1;
if(!vis[v])vis[v]=i+1;
}
memset(F,-1,sizeof(F));
for(int i=0; i<m; i++){
int u = R[i][0], v = R[i][1];
add(u,v,i+1);
add(v,u,i+1);
}
for(int i=0; i<n; i++){
adj[F[i]].eb(i);
if(deg[i]>1)adj[F[i+n]].eb(i+n);
}
run(P);
if(deg[P]>1)run(P+n);
for(int i=0; i<q; i++)answer(ans[i]);
}
