#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using ll = long long;
constexpr int INF = 1e9;
void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
std::vector<std::vector<std::array<int, 2>>> adj(n), rev(n);
for (int i = 0; i < m; i++) {
adj[r[i][0]].push_back({r[i][1], i});
adj[r[i][1]].push_back({r[i][0], i});
}
for (int i = 0; i < n; i++) {
if (adj[i].size() > 2) adj[i].resize(2);
for (const auto &[j, w] : adj[i]) {
rev[j].push_back({i, w});
}
}
std::vector<std::array<int, 2>> dist(n, {INF, INF});
std::vector<std::array<int, 2>> to_p(n, {INF, INF});
for (int tt = 0; tt < 2; tt++) {
// t = 0 means we take best edge from p
// t = 1 means we don't take best edge
if (tt == 1 && adj[p].size() == 1) break;
std::queue<std::array<int, 3>> bfs;
bfs.push({0, p, tt});
while (!bfs.empty()) {
const auto [t, u, f] = bfs.front();
bfs.pop();
if (dist[u][f] != INF) continue;
dist[u][f] = t;
int wt = adj[u][0][1];
for (const auto &[j, w] : rev[u]) {
if (f == 0 && w == wt && adj[u].size() > 1) continue;
if (f == 1 && w != wt && adj[u].size() > 1) continue;
int flag = w != adj[j][0][1];
bfs.push({t + 1, j, flag});
}
}
for (int i = 0; i < n; i++) {
to_p[i][tt] = dist[i][0];
}
dist.assign(n, {INF, INF});
}
int cycle_len = 0, node = p, flag = 0;
std::vector<std::array<bool, 2>> vis(n);
while (!vis[node][flag]) {
vis[node][flag] = true;
const auto [nxt, wt] = adj[node][flag];
if (adj[nxt].size() == 1) {
node = nxt, flag = 0;
} else {
node = nxt, flag = (adj[nxt][0][1] == wt);
}
cycle_len++;
}
if (node != p) cycle_len = INF;
for (int t = 0; t < q; t++) {
int k = g[t], res = 0;
for (int i = 0; i < n; i++) {
if (to_p[i][0] <= k && ((k - to_p[i][0]) % cycle_len == 0)) {
res++;
} else if (to_p[i][1] <= k && ((k - to_p[i][1]) % cycle_len == 0)) {
res++;
}
}
std::cout << res << '\n';
}
}
