#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int u) {
if (parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
void join(int u, int v) {
parent[find(v)] = find(u);
}
};
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);
vector<int> indeg(2*N, 0);
auto set_succ = [&](int u, int v) {
succ[u] = v;
++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]));
}
}
UnionFind U(2*N);
// for (int u = 0; u < 2*N; ++u) {
// cout << u << " " << succ[u] << endl;
// }
vector<int> lambda(2*N, -1);
vector<int> mu(2*N, -1);
vector<int> cycle(2*N, -1);
auto floyd_cycle = [&](int u) {
// cerr << "floyd " << u << endl;
// buscamos dos elementos en un ciclo
int a = succ[u];
int b = succ[succ[u]];
int i = 1;
while (a != b) {
if (mu[a] == 0) break;
++i;
a = succ[a];
b = succ[succ[b]];
}
if (mu[a] == 0) { // este ciclo ya lo hemos completado antes, no queremos repetir
lambda[u] = lambda[a];
cycle[u] = a;
mu[u] = i;
}
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];
cycle[a] = a;
U.join(a, succ[a]); // guardamos que forman parte del mismo grupo
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];
}
cycle[u] = a;
// mu[u] y cycle[u] calculados
}
// pasamos por los elementos de la cola para guardar la informacion
if (mu[u] > 1) U.join(u, succ[u]);
a = succ[u];
for (int i = 1; i < mu[u]; ++i) {
mu[a] = mu[u] - i;
lambda[a] = lambda[u];
cycle[a] = cycle[u];
if (mu[a] > 1) U.join(a, succ[a]);
a = succ[a];
}
};
// 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);
}
// floyd_cycle(5);
// floyd_cycle(2);
// for (int u = 0; u < 2*N; ++u) {
// cerr << "$ " << u << " " << mu[u] << " " << lambda[u] <<
// " " << cycle[u] << endl;
// }
// // comprobaciones
// for (int u = 0; u < 2*N; ++u) {
// if (indeg[u] == 0) assert(mu[u] > 0);
// assert(mu[u] != -1 and lambda[u] != -1 and cycle[u] != -1);
// if (mu[u] == 0) { // esta en un ciclo
// assert(cycle[u] == u);
// int v = u;
// for (int i = 0; i < lambda[u]; ++i) v = succ[v];
// assert(v == u);
// }
// else {
// int v = u;
// for (int i = 0; i < mu[u]-1; ++i) v = succ[v];
// assert(mu[v] == 1);
// v = succ[v];
// assert(mu[v] == 0);
// int w = v;
// for (int i = 0; i < lambda[u]; ++i) w = succ[w];
// assert(v == w);
// assert(cycle[w] == w);
// }
// }
vector<int> forwardP(lambda[P]+1, -1), forwardNP(lambda[N+P]+1, -1);
// si P esta en un ciclo calculamos todos los saltos
if (mu[P] == 0) {
forwardP[0] = P;
for (int i = 1; i < lambda[P]; ++i) {
forwardP[i] = succ[forwardP[i-1]];
}
}
// si N+P esta en un ciclo calculamos todos los saltos
if (mu[N+P] == 0) {
forwardNP[0] = N+P;
for (int i = 1; i < lambda[N+P]; ++i) {
forwardNP[i] = succ[forwardNP[i-1]];
}
}
// cout << lambda[P] << " " << mu[P] << " " << lambda[N+P] << " " << mu[N+P] << endl;
auto can_reach = [&](int u, int v, int k, vector<int>& forward) -> bool {
if (mu[u] > 0) { // caso u en una cola
if (U.find(u) == U.find(v)) { // los dos en la cola
int dist = mu[u] - mu[v];
return k == dist;
}
if (k < mu[u]) return false; // no podemos llegar al ciclo
k -= mu[u];
u = cycle[u];
}
// ahora u esta en un ciclo
if (U.find(u) == U.find(v)) { // ambos en el ciclo
int dist_inv = (-k%lambda[u] + lambda[u]) % lambda[u];
return forward[dist_inv] == u;
}
return false;
};
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], forwardP) or can_reach(u, N+P, G[it], forwardNP))
++cnt;
// for (int j = 0; j < K; ++j) u = succ[u];
// if (u == P or u == N+P) ++cnt;
}
answer(cnt);
}
}
