#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
const int MxN=150001, INF=1e9;
int mn[2*MxN], mx[2*MxN], nxt[2*MxN], dist[2*MxN][2], cyc[2];
vi prv[2*MxN];
bool v[2*MxN];
int cyc_find(int u, int st)
{
if(v[u]){
if(u==st) return 0;
else return -1;
}
v[u]=true;
int x=nxt[u];
int k=cyc_find(x, st);
if(k==-1) return -1;
else return k+1;
}
void calc_dist(int u, int in)
{
for(auto x : prv[u]){
if(dist[x][in]==-1){
dist[x][in]=dist[u][in]+1;
calc_dist(x, in);
}
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
FOR(i, 0, n)
{
mn[i]=mn[i+n]=-1;
mx[i]=mx[i+n]=-1;
nxt[i]=nxt[i+n]=-1;
}
FOR(i, 0, m)
{
int a=r[i][0], b=r[i][1];
if(mn[a]==-1) mn[a]=mn[a+n]=b;
else if(mx[a]==-1) mx[a]=mx[a+n]=b;
if(mn[b]==-1) mn[b]=mn[b+n]=a;
else if(mx[b]==-1) mx[b]=mx[b+n]=a;
}
FOR(i, 0, n)
{
int x=mn[i];
if(mx[x]==-1){
nxt[i]=x;
}
else if(mn[x]==i){
nxt[i]=x+n;
}
else{
nxt[i]=x;
}
}
FOR(i, n, 2*n)
{
if(mx[i]==-1) continue;
int x=mx[i];
if(mx[x]==-1){
nxt[i]=x;
}
else if(mn[x]==i-n){
nxt[i]=x+n;
}
else{
nxt[i]=x;
}
}
FOR(i, 0, 2*n)
{
dist[i][0]=dist[i][1]=-1;
if(nxt[i]!=-1) prv[nxt[i]].pb(i);
}
cyc[0]=cyc_find(p, p);
FOR(i, 0, 2*n) v[i]=false;
cyc[1]=cyc_find(p+n, p+n);
dist[p][0]=0; calc_dist(p, 0);
dist[p+n][1]=0; calc_dist(p+n, 1);
FOR(i, 0, q)
{
int ans=0;
FOR(j, 0, n)
{
FOR(k, 0, 2)
if(dist[j][k]!=-1){
if(cyc[k]==-1){
if(dist[j][k]==g[i]) ans++;
}
else if(g[i]>=dist[j][k] && (g[i]-dist[j][k])%cyc[k]==0) ans++;
}
}
answer(ans);
}
}
