#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC target("avx,avx2")
#include "garden.h"
#include "gardenlib.h"
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
const int LOG = 31;
vector<vector<int>> edges(N);
for (int i = 0; i < M; ++i) {
edges[R[i][0]].push_back(R[i][1]);
edges[R[i][1]].push_back(R[i][0]);
}
vector<int> next(2 * N, -1);
for (int i = 0; i < N; ++i) {
int x = edges[i][0];
next[2 * i] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
x = ((int) edges[i].size() == 1 ? edges[i][0] : edges[i][1]);
next[2 * i + 1] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
}
vector<vector<int>> lift(LOG, vector<int>(2 * N));
lift[0] = next;
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i < 2 * N; ++i) {
lift[j][i] = lift[j - 1][lift[j - 1][i]];
}
}
auto get = [&](int i, int k) {
for (int j = LOG - 1; j >= 0; --j) {
if (k >= 1 << j) {
i = lift[j][i];
k -= 1 << j;
}
}
return i;
};
for (int j = 0; j < Q; ++j) {
int k = G[j], cnt = 0;
for (int i = 0; i < N; ++i) {
if (get(i * 2, k) / 2 == P) ++cnt;
}
answer(cnt);
}
}
