#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
vector<int> adj0(N, -1);
vector<int> adj1(N, -1);
for (int i = 0; i < M; i++) {
int u = R[i][0];
int v = R[i][1];
if (adj0[u] == -1) adj0[u] = v;
else if (adj1[u] == -1) adj1[u] = v;
if (adj0[v] == -1) adj0[v] = u;
else if (adj1[v] == -1) adj1[v] = u;
}
for (int i = 0; i < N; i++) {
if (adj1[i] == -1) adj1[i] = adj0[i];
}
auto next_state = [&](int state) -> int {
int u = state / 2;
int s = state % 2;
int w = (s == 0) ? adj0[u] : adj1[u];
if (adj0[w] == u) return 2 * w + 1;
else return 2 * w;
};
int total_states = 2 * N;
vector<int> cycle_size(total_states, 0);
vector<int> first_visit(total_states, -1);
vector<bool> in_cycle(total_states, false);
int time_stamp = 0;
for (int start = 0; start < total_states; start++) {
if (first_visit[start] != -1) continue;
int slow = start, fast = start;
do {
slow = next_state(slow);
fast = next_state(next_state(fast));
} while (first_visit[slow] == -1 && first_visit[fast] == -1 && slow != fast);
if (first_visit[slow] != -1) continue;
if (slow == fast) {
int cycle_start = slow;
vector<int> cycle_nodes;
int cur = cycle_start;
do {
cycle_nodes.push_back(cur);
cur = next_state(cur);
} while (cur != cycle_start);
int len = cycle_nodes.size();
for (int node : cycle_nodes) {
cycle_size[node] = len;
in_cycle[node] = true;
}
}
int cur = start;
int cnt = 0;
while (first_visit[cur] == -1) {
first_visit[cur] = time_stamp++;
cur = next_state(cur);
cnt++;
}
}
int t0 = 2 * P;
int t1 = 2 * P + 1;
vector<int> dist0(total_states, -1);
vector<int> dist1(total_states, -1);
vector<vector<int>> rev_adj(total_states);
for (int i = 0; i < total_states; i++) {
int j = next_state(i);
rev_adj[j].push_back(i);
}
queue<int> q0;
dist0[t0] = 0;
q0.push(t0);
while (!q0.empty()) {
int u = q0.front(); q0.pop();
for (int v : rev_adj[u]) {
if (dist0[v] == -1) {
dist0[v] = dist0[u] + 1;
q0.push(v);
}
}
}
queue<int> q1;
dist1[t1] = 0;
q1.push(t1);
while (!q1.empty()) {
int u = q1.front(); q1.pop();
for (int v : rev_adj[u]) {
if (dist1[v] == -1) {
dist1[v] = dist1[u] + 1;
q1.push(v);
}
}
}
int C0 = cycle_size[t0];
int C1 = cycle_size[t1];
for (int idx = 0; idx < Q; idx++) {
long long K = G[idx];
int ans = 0;
for (int u = 0; u < N; u++) {
int s0 = 2 * u;
if (dist0[s0] != -1) {
if (C0 == 0) {
if (dist0[s0] == K) ans++;
} else {
if (K >= dist0[s0] && (K - dist0[s0]) % C0 == 0)
ans++;
}
}
if (dist1[s0] != -1) {
if (C1 == 0) {
if (dist1[s0] == K) ans++;
} else {
if (K >= dist1[s0] && (K - dist1[s0]) % C1 == 0)
ans++;
}
}
}
answer(ans);
}
}
