#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int MAXN = 300100, MAXK = 31;
int n, m, p;
vii adj[MAXN];
int par[2*MAXN][MAXK];
int getId (int v, int b) {
return (b*n + v);
}
/*int lift (int v, ll x) {
FOR(i, 0, MAXK-1)
if (x & (1ll<<i))
v = par[v][i];
return v;
}
int getAns (ll k){
int ret = 0;
//k--;
FOR(i, 0, n-1) {
int lifted = lift(i,k);
// cout << " k = " << k << " i = " << i << " lifted = " << lifted << endl;
if (lifted == getId(p, 0) || lifted == getId(p, 1)) {
ret++;
}
}
return ret;
}*/
bool vis[MAXN];
stack<int> cycle;
int toP[MAXN][2];
bool inCycle[MAXN][2];
int cycleLen[2];
void checkCycle (int v, int st, bool b) {
vis[v] = true;
int u = par[v][0];
cycle.push(v);
if (!vis[u])
checkCycle(u, st, b);
else {
if (u == st) {
inCycle[st][b] = true;
cycleLen[b] = (int)cycle.size();
int cur = 0;
while (!cycle.empty()) {
int x = cycle.top();
inCycle[x][b] = true;
cycle.pop();
cur++;
if (x != st) toP[x][b] = cur;
}
} else {
while (!cycle.empty()) {
cycle.pop();
}
}
}
}
void dfs (int v, bool b) {
if (inCycle[v][b]) return;
toP[v][b] = -1;
vis[v] = true;
int u = par[v][0];
if (!vis[u])
dfs(u, b);
if (toP[u][b] == -1) toP[v][b] = -1;
else toP[v][b] = toP[u][b] + 1;
if(v==getId(p,b)) toP[v][b] = 0;
}
int getAns (ll k) {
int ret = 0;
FOR(i, 0, n-1) {
bool ok = false;
FOR(b,0,1) {
// cout << " i = " << i << " b = " << b << " toP = " << toP[i][b] << " incycle= " << inCycle[i][b] << endl;
if (toP[i][b] == -1) continue;
ll rem = k - toP[i][b];
if (rem > 0 && cycleLen[b] > 0 && ((rem % cycleLen[b]) == 0))
ok = true;
else if (rem == 0) ok = true;
}
if (ok) ret++;
}
return ret;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P;
FOR(i, 0, m-1) {
int u = R[i][0];
int v = R[i][1];
adj[u].pb({i, v});
adj[v].pb({i, u});
}
FOR(v, 0, n-1) FOR(b, 0, 1) {
int fr = getId(v, b);
int u = (b < (int)adj[v].size() ? adj[v][b].s : adj[v][0].s);
int b2 = (adj[u][0].s == v);
int to = getId(u, b2);
par[fr][0] = to;
// cout << " fr = " << fr << " to = " << to << endl;
}
/*FOR(j, 1, MAXK-1) FOR(i, 0, getId(n-1, 1))
par[i][j] = par[par[i][j-1]][j-1];*/
int mxn = getId(n-1, 1);
//cout << " a" << endl;
FOR(b, 0, 1) {
FOR(i, 0, mxn) vis[i] = false;
checkCycle(getId(p, b), getId(p, b), b);
}
//cout << " b " << endl;
FOR(b, 0, 1) {
FOR(i, 0, mxn) vis[i] = false;
FOR(i, 0, mxn) {
if (!vis[i])
dfs(i, b);
}
}
//cout << " c" << endl;
for(int i=0; i<Q; i++) {
ll k = G[i];
int ans = getAns (k);
answer(ans);
}
}
