#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<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 u, int v) {
if (adj[v][0] == u)
return N+v;
else
return v;
};
const int J = 29;
vector<int> succ(2*N, -1), indeg(2*N, 0);
vector<vector<int>> rev(2*N);
auto set_succ = [&](int u, int v) {
succ[u] = v;
rev[v].push_back(u);
++indeg[v];
};
for (int i = 0; i < N; ++i) {
set_succ(node(-1, i), node(i, adj[i][0]));
for (int v : adj[i]) {
if (v != adj[i][0] or adj[i].size() == 1)
set_succ(node(v, i), node(i, adj[i][0]));
else
set_succ(node(v, i), node(i, adj[i][1]));
}
}
vector<int> lambda(2*N, -1), mu(2*N, -1);
auto floyd_cycle = [&](int u) {
// buscamos dos elementos en un ciclo
int a = succ[u];
int b = succ[succ[u]];
int i = 1;
while (a != b) {
if (mu[a] != -1) break;
++i;
a = succ[a];
b = succ[succ[b]];
}
if (mu[a] != -1) { // a partir de <a> ya se ha calculado
lambda[u] = lambda[a];
mu[u] = i;
// pasamos por los elementos de la cola hasta <a> para guardar la informacion
b = succ[u];
for (int j = 1; j < mu[u]; ++j) {
mu[b] = mu[u] - j;
lambda[b] = lambda[u];
b = succ[b];
}
}
else {
// ahora iteramos el ciclo para calcular su longitud
b = succ[a];
lambda[u] = 1; // longitud ciclo
while (a != b) {
++lambda[u];
b = succ[b];
}
// lambda[u] calculada
// pasamos por todos los elementos del ciclo para guardar la informacion
for (int i = 0; i < lambda[u]; ++i) {
mu[a] = 0;
lambda[a] = lambda[u];
a = succ[a];
}
// reiniciamos punteros y ahora calculamos longitud de la cola e inicio del ciclo
a = u;
b = u;
for (int i = 0; i < lambda[u]; ++i) {
b = succ[b];
}
mu[u] = 0; // longitud cola
while (a != b) {
++mu[u];
a = succ[a];
b = succ[b];
}
// mu[u] calculada
}
};
// empezamos a hacer floyd por las hojas, para procesar colas eficientemente
for (int u = 0; u < 2*N; ++u) {
if (indeg[u] == 0) floyd_cycle(u);
}
// los que queden son ciclos puros
for (int u = 0; u < 2*N; ++u) {
if (mu[u] == -1) floyd_cycle(u);
}
auto get_rev_dists = [&](int u) {
vector<int> dist(2*N, -1);
queue<int> q;
dist[u] = 0;
q.push(u);
while (not q.empty()) {
int i = q.front(); q.pop();
for (int j : rev[i]) {
if (dist[j] == -1) {
q.push(j);
dist[j] = dist[i] + 1;
}
}
}
return dist;
};
auto can_reach = [&](int u, int v, int k, const vector<int>& distv) -> bool {
if (distv[u] == -1) return false; // otra componenete
if (k < distv[u]) return false; // no llegamos
if (distv[u] == k) return true; // directamente
if (mu[v] == 0 and (k - distv[u]) % lambda[v] == 0) // dando vueltas al ciclo
return true;
return false;
};
vector<int> distP = get_rev_dists(P), distNP = get_rev_dists(N+P);
for(int it = 0; it < Q; ++it) {
int cnt = 0;
for (int i = 0; i < N; ++i) {
int u = node(-1, i);
if (can_reach(u, P, G[it], distP) or can_reach(u, N+P, G[it], distNP))
++cnt;
}
answer(cnt);
}
}
