#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
pair <int, int> edge[300001];
int a[300001],b[300001],mx[150001],mx2[150001],nxt[300001],ch[300001],t[300001],id,cycle[300001],d[300001],cnt[300001],res;
vector <int> ke[300001],ve[300001],tmp;
void dfs(int u, int i){
ch[i]|=t[u];
b[u]=a[u];
for (int v:ke[u]){
d[v]=d[u]+1;
dfs(v,i);
b[u]|=b[v];
}
}
void dfs2(int u, int k, int i, int p, int sz){
if (!b[u])
return;
cnt[d[u]]+=t[u];
if (a[u]){
if (d[u]>=k)
res+=(!!cnt[d[u]-k]);
else
res+=t[ve[i][(p+k-d[u])%sz]];
}
for (int v:ke[u])
dfs2(v,k,i,p,sz);
cnt[d[u]]-=t[u];
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
for (int i=0;i<M;i++){
edge[M-i-1]={R[i][0],R[i][1]};
edge[M*2-i-1]={R[i][1],R[i][0]};
}
memset(mx,-1,sizeof(mx));
memset(mx2,-1,sizeof(mx2));
for (int i=0;i<M*2;i++){
int u=edge[i].first;
if (mx[u]%M<i%M){
mx2[u]=mx[u];
mx[u]=i;
}
else if (mx2[u]%M<i%M)
mx2[u]=i;
}
for (int i=0;i<N;i++)
a[mx[i]]=1;
for (int i=0;i<M*2;i++){
int v=edge[i].second;
if (mx[v]%M==i%M)
nxt[i]=(mx2[v]==-1?mx[v]:mx2[v]);
else
nxt[i]=mx[v];
t[i]=(v==P);
}
for (int i=0;i<M*2;i++){
if (!ch[i]){
tmp.clear();
int u=i;
while (true){
u=nxt[u];
if (ch[u]>1){
for (int j:tmp)
ch[j]=2;
break;
}
if (ch[u]==1){
int p=0;
for (int j=0;j<tmp.size();j++)
if (tmp[j]==u)
p=j;
for (int j=p;j<tmp.size();j++){
ve[id].push_back(tmp[j]);
cycle[tmp[j]]=1;
}
for (int j:tmp)
ch[j]=2;
id++;
break;
}
tmp.push_back(u);
ch[u]=1;
}
}
}
for (int i=0;i<M*2;i++)
if (!cycle[i])
ke[nxt[i]].push_back(i);
for (int i=0;i<id;i++){
ch[i]=0;
for (int j:ve[i])
dfs(j,i);
}
for (int i=0;i<Q;i++){
res=0;
for (int j=0;j<id;j++)
if (ch[j])
for (int k=0;k<ve[j].size();k++)
dfs2(ve[j][k],G[i]-1,j,k,ve[j].size());
answer(res);
}
}
