#include "garden.h"
#include <bits/stdc++.h>
#include "gardenlib.h"
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
// build graph
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
auto node = [&](int p, int u) {
if (p == adj[u][0]) return N + u;
return u;
};
// build functional graph
vector<int> next(2 * N, -1), ideg(2 * N, 0);
vector<vector<int>> prev(2 * N);
auto connect = [&](int u, int v) {
ideg[v]++;
next[u] = v;
prev[v].push_back(u);
};
for (int i = 0; i < N; i++) {
connect(node(-1, i), node(i, adj[i][0]));
for (auto v : adj[i]) {
if (v != adj[i][0] || adj[i].size() == 1)
connect(node(v, i), node(i, adj[i][0]));
else
connect(node(v, i), node(i, adj[i][1]));
}
}
// t + c
vector<int> floydT(2 * N, -1), floydC(2 * N, -1);
auto floyd = [&](int u) {
int fast = u, slow = u;
int len = 0;
while (true) {
len++;
fast = next[next[fast]];
slow = next[slow];
if (fast == slow) break;
if (floydC[slow] != -1) break;
}
if (floydC[slow] != -1) {
fast = u;
for (int i = 0; i < len; i++) {
floydC[fast] = floydC[slow];
floydT[fast] = floydT[slow] + len - i;
fast = next[fast];
}
return;
}
int c = 0;
while (true) {
c++;
fast = next[fast];
if (fast == slow) break;
}
fast = u;
for (int i = 0; i < c; i++) {
floydC[slow] = c;
floydT[slow] = 0;
slow = next[slow];
fast = next[fast];
}
int t = 0;
slow = u;
while (true) {
t++;
slow = next[slow];
fast = next[fast];
if (fast == slow) break;
}
slow = u;
for (int i = 0; i < t; i++) {
floydC[slow] = c;
floydT[slow] = t - i;
slow = next[slow];
}
};
for (int i = 0; i < N; i++) {
if (ideg[i] == 0 || floydC[i] == -1) floyd(i);
}
auto dist = [&](int u) {
vector<int> dist(2 * N, -1);
queue<int> q;
dist[u] = 0;
q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : prev[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
};
auto reachable = [&](int u, int v, int k, const vector<int>& dist) {
if (dist[u] == -1) return false;
if (dist[u] == k) return true;
if (floydT[v] == 0 && k > dist[u] && (k - dist[u]) % floydC[v] == 0)
return true;
return false;
};
vector<int> distP = dist(P), distNP = dist(N + P);
for (int i = 0; i < Q; i++) {
int cnt = 0;
for (int j = 0; j < N; j++) {
if (reachable(j, P, G[i], distP) || reachable(j, N + P, G[i], distNP))
cnt++;
}
answer(cnt);
}
}
