#include <vector>
#include <utility>
#include <cassert>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
using pii = pair<int, int>;
constexpr int INF = 1e9;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
vector<int> to(2*N, -1);
for (int i = 0; i < M; i++) {
const bool first0 = to[R[i][0]] == -1;
const bool first1 = to[R[i][1]] == -1;
if (to[R[i][0]] == -1) {
to[R[i][0]] = R[i][1] + (first1 ? N : 0);
} else if (to[R[i][0] + N] == -1) {
to[R[i][0] + N] = R[i][1] + (first1 ? N : 0);
}
if (to[R[i][1]] == -1) {
to[R[i][1]] = R[i][0] + (first0 ? N : 0);
} else if (to[R[i][1] + N] == -1) {
to[R[i][1] + N] = R[i][0] + (first0 ? N : 0);
}
}
for (int i = 0; i < N; i++) {
if (to[i+N] == -1) {
to[i+N] = to[i];
}
}
vector<vector<int>> from(2*N);
for (int i = 0; i < 2*N; i++) {
if (to[i] != -1) from[to[i]].push_back(i);
}
// or -1
auto cycle_length = [&](int x) -> int {
int len = 0, curr = x;
while (len < 2*N+1 && to[curr] != -1) {
len++;
curr = to[curr];
if (curr == x) return len;
}
return -1;
};
auto dfs = [&](auto &&dfs, int curr, vector<int> &dist) -> void {
assert(dist[curr] != -1);
for (int c: from[curr]) {
if (dist[c] != -1) continue;
dist[c] = dist[curr]+1;
dfs(dfs, c, dist);
}
};
int len = cycle_length(P), len2 = cycle_length(P+N);
if (len == -1) len = INF;
if (len2 == -1) len2 = INF;
vector<int> dist(2*N, -1), dist2(2*N, -1);
dist[P] = 0; dist2[P+N] = 0;
dfs(dfs, P, dist);
dfs(dfs, P+N, dist2);
vector<int> byD(2*N, 0), byD2(2*N, 0);
for (int i = 0; i < N; i++) {
if (dist[i] != -1) {
byD[dist[i] % len]++;
}
if (dist2[i] != -1) {
byD2[dist2[i] % len2]++;
}
}
for(int q = 0; q < Q; q++) {
int ans = 0;
if (G[q] % len < 2*N) ans += byD[G[q] % len];
if (G[q] % len2 < 2*N) ans += byD2[G[q] % len2];
answer(ans);
}
}
