#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define v vector
#define pii pair<int,int>
#define ll long long
#define pli pair<long long, int>
#define fi first
#define se second
using namespace std;
const int LIMIT = 29;
void dfs(v<v<int>> &adj, int node, int dist, v<int> &dists) {
if (dists[node] != -1) return;
dists[node] = dist;
for (int nex : adj[node]) {
dfs(adj, nex, dist + 1, dists);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
v<int> first(N, -1), second(N, -1), next(2 * N, -1);
for (int i = 0; i < M; i++) {
int a = R[i][0], b = R[i][1];
if (first[a] == -1) first[a] = b;
else if (second[a] == -1) second[a] = b;
if (first[b] == -1) first[b] = a;
else if (second[b] == -1) second[b] = a;
}
for (int i = 0; i < N; i++) {
if (second[i] == -1) second[i] = first[i];
}
for (int i = 0; i < N; i++) {
next[2 * i] = (first[first[i]] == i) ? first[i] * 2 + 1 : first[i] * 2;
next[2 * i + 1] = (first[second[i]] == i) ? second[i] * 2 + 1 : second[i] * 2;
}
int p_cycle0 = 1e9 + 100, p_cycle1 = 1e9 + 100;
int cur = 2 * P;
for (int i = 0; i < 2 * N; i++) {
cur = next[cur];
if (cur == 2 * P) {
p_cycle0 = i + 1;
break;
}
}
cur = 2 * P + 1;
for (int i = 0; i < 2 * N; i++) {
cur = next[cur];
if (cur == 2 * P + 1) {
p_cycle1 = i + 1;
break;
}
}
v<v<int>> adj(2 * N);
for (int i = 0; i < 2 * N; i++) {
adj[next[i]].push_back(i);
}
v<int> dists0(2 * N, -1), dists1(2 * N, -1);
dfs(adj, 2 * P, 0, dists0);
dfs(adj, 2 * P + 1, 0, dists1);
for (int i = 0; i < Q; i++) {
int K = G[i], count = 0;
for (int j = 0; j < N; j++) {
if ((dists0[2 * j] != -1 && dists0[2 * j] <= K && (K - dists0[2 * j]) % p_cycle0 == 0) ||
(dists1[2 * j] != -1 && dists1[2 * j] <= K && (K - dists1[2 * j]) % p_cycle1 == 0)) {
count++;
}
}
answer(count);
}
}
