#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
typedef long long ll;
const int N=150000;
const int M=150000;
int p;
array<int,2> opt[N];
int endpoint[2*M];
int to[2*M];
array<int,2> precycle[2*M];
array<int,2> incycle[2*M];
bool partcycle[2*M];
int cyclelen[2*M];
int st[2*M];
vector<int> now;
int one(array<int,2> &a)
{
int t=0;
while(t<2&&a[t]!=-1) t++;
return t;
}
void dfs(int a)
{
int b=to[a];
st[a]=1;
now.push_back(a);
if(st[b]==1)
{
int sz=now.size();
int pos=sz-1;
while(now[pos]!=b) pos--;
int len=sz-pos;
vector<int> v;
for(int i=pos;i<sz;i++)
{
partcycle[now[i]]=1;
cyclelen[now[i]]=len;
if(endpoint[now[i]]==p) v.push_back(i);
}
assert(v.size()<=2);
for(int i=pos;i<sz;i++)
{
for(int x:v)
{
int t=(((x-i)%len)+len)%len;
incycle[now[i]][one(incycle[now[i]])]=t;
}
}
}
else
{
if(st[b]==0) dfs(b);
if(!partcycle[a])
{
cyclelen[a]=cyclelen[b];
for(int i=0;i<2;i++) if(incycle[b][i]!=-1) incycle[a][i]=incycle[b][i]+1;
for(int i=0;i<2;i++) if(precycle[b][i]!=-1) precycle[a][i]=precycle[b][i]+1;
}
if(!partcycle[a]&&endpoint[a]==p) precycle[a][one(precycle[a])]=0;
}
st[a]=2;
now.pop_back();
}
void count_routes(int n,int m,int tp,int r[][2],int q,int g[])
{
for(int i=0;i<n;i++) opt[i]={-1,-1};
for(int i=0;i<2*m;i++)
{
precycle[i]=incycle[i]={-1,-1};
cyclelen[i]=-1;
}
auto add_edge=[&](int x,int id)
{
int t=one(opt[x]);
if(t<2) opt[x][t]=id;
};
for(int i=0;i<m;i++)
{
int a=r[i][0],b=r[i][1];
endpoint[2*i]=b;
endpoint[2*i+1]=a;
add_edge(a,2*i);
add_edge(b,2*i+1);
}
for(int i=0;i<2*m;i++)
{
int x=endpoint[i];
to[i]=opt[x][(opt[x][0]/2==i/2&&opt[x][1]!=-1)];
}
p=tp;
for(int i=0;i<2*m;i++) if(st[i]==0) dfs(i);
for(int i=0;i<q;i++)
{
int k=g[i]-1;
int res=0;
for(int j=0;j<n;j++)
{
bool ok=0;
int a=opt[j][0];
for(int t=0;t<2;t++)
{
ok|=(precycle[a][t]==k);
if(incycle[a][t]!=-1) ok|=(k>=incycle[a][t]&&((k-incycle[a][t])%cyclelen[a])==0);
}
res+=ok;
}
answer(res);
}
}
