#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
vector<int> deg(N);
vector<int> best(N, -1);
for (int i = 0; i < M; ++i) {
for (int z = 0; z < 2; ++z) {
++deg[R[i][z]];
if (best[R[i][z]] == -1) best[R[i][z]] = i;
}
}
vector<int> nxt(N * 2, -1);
for (int i = 0; i < M; ++i) {
for (int z = 0; z < 2; ++z) {
int to = R[i][!z];
if (best[R[i][!z]] == i && deg[R[i][!z]] > 1) to += N;
if (nxt[R[i][z]] == -1) nxt[R[i][z]] = to;
else if (nxt[R[i][z] + N] == -1) nxt[R[i][z] + N] = to;
}
}
vector<vector<int>> adj(2 * N);
for (int i = 0; i < N; ++i) {
adj[nxt[i]].emplace_back(i);
if (deg[i] > 1) adj[nxt[i + N]].emplace_back(i + N);
}
vector<pair<int, int>> qs;
for (int i = 0; i < Q; ++i) qs.emplace_back(G[i], i);
sort(qs.begin(), qs.end());
vector<int> ans(Q);
auto go = [&](int start) {
vector<int> dist(2 * N, -1);
vector<int> q;
dist[start] = 0;
q.emplace_back(start);
for (int i = 0; i < int(q.size()); ++i) {
int v = q[i];
for (int u : adj[v]) if (dist[u] == -1) {
dist[u] = dist[v] + 1;
q.emplace_back(u);
}
}
vector<int> dists;
for (int v : q) if (v < N) dists.emplace_back(dist[v]);
int len = 0;
vector<bool> visited(2 * N);
int v = start;
while (!visited[v]) {
visited[v] = true;
v = nxt[v];
++len;
}
if (v != start) len = -1;
vector<int> cnts(2 * N);
int ptr = 0;
for (int i = 0; i < Q; ++i) {
while (ptr < int(dists.size()) && dists[ptr] <= qs[i].first) {
int cur = dists[ptr++];
if (len != -1) cur %= len;
++cnts[cur];
}
int cur = qs[i].first;
if (len != -1) cur %= len;
if (cur < 2 * N) ans[qs[i].second] += cnts[cur];
}
};
go(P);
if (deg[P] > 1) go(P + N);
for (int i = 0; i < Q; ++i) answer(ans[i]);
}
