#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=300010, inf=2e9;
int n, nxt[MX], Q1, Q2; // in, out
void debug(){
for(int i=0; i<n; i++)
cout<<nxt[i]<<' ';
cout<<"\n\n";
}
int fir[MX], scd[MX];
void init(int V, int E, int P, int R[][2]){
fill(fir, fir+n, -1);
fill(scd, scd+n, -1);
// u->v: 0, v->u: 1
for(int i=0; i<E; i++){
int u=R[i][0], v=R[i][1];
if(fir[u]<0) fir[u]=2*i;
else if(scd[u]<0) scd[u]=2*i;
if(fir[v]<0) fir[v]=2*i+1;
else if(scd[v]<0) scd[v]=2*i+1;
}
for(int i=0; i<E; i++){
int u=R[i][0], v=R[i][1];
// u->v, v->u
if(fir[v]==2*i+1 && scd[v]>=0) nxt[2*i]=scd[v];
else nxt[2*i]=fir[v];
if(fir[u]==2*i && scd[u]>=0) nxt[2*i+1]=scd[u];
else nxt[2*i+1]=fir[u];
}
Q1=fir[P]+(fir[P]%2==0 ? 1 : -1), Q2=fir[P];
}
int D1[MX], D2[MX], cyc1, cyc2;
bool vis1[MX], vis2[MX], vis3[MX];
int dep[MX], now;
void dfs1(int v){
vis1[v]=true; dep[v]=++now;
if(v==Q1) D1[v]=0;
int x=nxt[v];
if(!vis1[x]) dfs1(x);
if(x==Q1) cyc1=dep[v]-dep[x]+1;
D1[v]=min(D1[v], D1[x]+1);
}
void dfs2(int v){
vis2[v]=true; dep[v]=++now;
if(v==Q2) D2[v]=0;
int x=nxt[v];
if(!vis2[x]) dfs2(x);
if(x==Q2) cyc2=dep[v]-dep[x]+1;
D2[v]=min(D2[v], D2[x]+1);
}
void dfs3(int v){
vis3[v]=true;
int x=nxt[v];
if(!vis3[x]) dfs3(x);
D1[v]=min(D1[v], (D1[x]==inf ? inf : D1[x]+1));
D2[v]=min(D2[v], (D2[x]==inf ? inf : D2[x]+1));
}
void prec(){
fill(D1, D1+n, inf); D1[Q1]=0;
fill(D2, D2+n, inf); D2[Q2]=0;
cyc1=cyc2=0;
dfs1(Q1);
dfs2(Q2);
for(int i=0; i<n; i++)
vis3[i]=vis1[i]&&vis2[i];
for(int i=0; i<n; i++){
if(vis3[i]) continue;
dfs3(i);
}
}
bool valid(int d, int k, int c){
if(d>=inf/2) return false;
return (c==0 && k==d) || (c!=0 && d<=k && (k-d)%c==0);
}
int solve(int k, int V){
int ans=0;
for(int i=0; i<V; i++){
int e=fir[i];
ans+=(valid(D1[e]+1, k, cyc1) || valid(D2[e], k, cyc2));
}
return ans;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n=2*M;
init(N,M,P,R);
prec();
for(int i=0; i<Q; i++)
answer(solve(G[i], N));
}
