#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
vector<vector<int>> to(n);
for (int i = 0; i < m; ++i) {
int a = r[i][0], b = r[i][1];
if ((int)to[a].size() < 2) to[a].emplace_back(b);
if ((int)to[b].size() < 2) to[b].emplace_back(a);
}
vector<int> nxt(2 * n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2 && j < (int)to[i].size(); ++j) {
int x = to[i][j];
int node = (to[x][0] == i) * n + x;
nxt[j * n + i] = node;
}
}
for (int i = n; i < 2 * n; ++i) if (nxt[i] == -1) nxt[i] = nxt[i - n];
vector<vector<int>> adj(2 * n);
for (int i = 0; i < 2 * n; ++i) {
adj[nxt[i]].emplace_back(i);
}
vector<bool> vis(2 * n);
function<void(int, int , int&, vector<int>&)>
DFS = [&](int node, int stop, int &cycle_len, vector<int> &dist) {
if (vis[node]) {
return;
}
vis[node] = true;
for (int &x : adj[node]) {
if (x == stop) {
cycle_len = 1 + dist[node];
continue;
}
dist[x] = 1 + dist[node];
DFS(x, stop, cycle_len, dist);
}
};
const int INF = (int)1e9 + 10;
vector<int> cycle(2, INF);
vector<vector<int>> dist(2, vector<int>(2 * n, -1));
dist[0][p] = dist[1][p + n] = 0;
DFS(p, p, cycle[0], dist[0]);
fill(vis.begin(), vis.end(), false);
DFS(p + n, p + n, cycle[1], dist[1]);
vector<vector<int>> cnt_dist(2, vector<int>(2 * n));
for (int i = 0; i < 2; ++i) {
for (int node = 0; node < n; ++node) { // doar nodurile "bune" conteaza ca doar din ele pot incepe
if (dist[i][node] == -1) continue;
++cnt_dist[i][dist[i][node]];
}
}
for (int it = 0; it < q; ++it) {
int k = qrs[it];
int ans = 0;
for (int i = 0; i < 2; ++i) {
for (int d = k % cycle[i]; d <= n && d <= k; d += cycle[i])
ans += cnt_dist[i][d];
}
answer(ans);
}
}
