#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pb push_back
using ll = long long;
int n, m, p, q;
vector<vector<pair<int, int>>> min_edge;
vector<vector<pair<int, int>>> graph;
vector<vector<int>> edges;
vector<int> act;
vector<int> D, C;
int get_dest(pair<int, int> edge) {
return edges[edge.first][edge.second];
}
pair<int, int> get_next(pair<int, int> edge) {
int v = get_dest(edge);
if(edge.first != min_edge[v][0].first) {
return min_edge[v][0];
}
else {
return min_edge[v][1];
}
}
int get_id(pair<int, int> edge) {
return edge.first + (m * edge.second);
}
constexpr int UNVISITED = (-1);
constexpr int UNREACHABLE = (1e9);
int timer = 0;
void dfs_cyc(pair<int, int> edge) {
int id = get_id(edge);
act[id] = ++timer;
auto nxt = get_next(edge);
int nxt_id = get_id(nxt);
if(act[nxt_id]) {
C[id] = C[nxt_id] = (act[id] - act[nxt_id]) + 1;
}
else {
if(C[nxt_id] == UNVISITED) {
dfs_cyc(nxt);
}
}
C[id] = C[nxt_id];
act[id] = 0;
}
void dfs(pair<int, int> edge) {
int v = get_dest(edge);
int id = get_id(edge);
D[id] = UNREACHABLE;
if(v == p) {
D[id] = 1;
return;
}
auto nxt = get_next(edge);
int new_id = get_id(nxt);
if(D[new_id] == UNVISITED) {
dfs(nxt);
}
if(D[new_id] == UNREACHABLE) {
D[id] = UNREACHABLE;
}
else {
D[id] = D[new_id] + 1;
}
}
void count_routes(int N, int M, int P, int _edges[][2], int Q, int _G[]) {
n = N, m = M, p = P, q = Q;
edges.resize(m, vector<int>(2));
loop(i, 0, m-1) {
loop(j, 0, 1) {
edges[i][j] = _edges[i][j];
}
}
graph.resize(n);
loop(i, 0, m-1) {
int a = edges[i][0];
int b = edges[i][1];
graph[a].pb({ i, 1 });
graph[b].pb({ i, 0 });
}
min_edge.resize(n, vector<pair<int, int>>(2, { 1e9, (-1) }));
D.resize(2 * m, UNVISITED);
C.resize(2 * m, UNVISITED);
act.resize(2 * m, 0);
loop(i, 0, n-1) {
for(pair<int, int> state : graph[i]) {
if(state < min_edge[i][0]) {
min_edge[i][1] = min_edge[i][0];
min_edge[i][0] = state;
}
else if(state < min_edge[i][1]) {
min_edge[i][1] = state;
}
}
if(sz(graph[i]) == 1) {
min_edge[i][1] = min_edge[i][0];
}
}
loop(i, 0, n-1) {
dfs_cyc(min_edge[i][0]);
}
loop(i, 0, n-1) {
auto e = min_edge[i][0];
if(D[get_id(e)] == UNVISITED) {
dfs(e);
}
}
// loop(i, 0, n-1) {
// int id = get_id(min_edge[i][0]);
// // cout << "dist_from_p[" << i << "] = " << D[id] << ", " << "cycle_len[" << i << "] = " << C[id] << '\n';
// }
loop(qi, 0, q-1) {
int k = _G[qi];
if(k == 0) {
answer(1);
continue;
}
int res = 0;
loop(i, 0, n-1) {
int id = get_id(min_edge[i][0]);
int d = D[id];
int c = C[id];
if(k % c == d % c) {
++res;
}
}
answer(res);
}
}
