#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
int V, E;
vector<int> deg;
vector<int> adj;
vector<vector<int>> revAdj;
vector<int> distP, distPV;
vector<int> cycleLen;
vector<int> prefModP, prefModPV;
void BFS (vector<int>& dist, int source) {
dist.assign(2*V, INF);
dist[source] = 0;
deque<int> DQ;
DQ.push_back(source);
while (!DQ.empty()) {
int on = DQ.front();
DQ.pop_front();
for (int prv : revAdj[on]) {
if (dist[prv] > dist[on] + 1) {
dist[prv] = dist[on] + 1;
DQ.push_back(prv);
}
}
}
}
void makePref (vector<int>& dist, vector<int>& pref, int len) {
assert((int)dist.size() == 2*V);
pref.assign(2*V, 0);
for (int i = 0; i < V; i++) {
if (dist[i] != INF) {
assert(dist[i] < 2*V && dist[i] >= 0);
pref[dist[i]]++;
}
}
for (int i = 0; i < 2*V; i++) {
if (i >= len && len > 0) {
pref[i] += pref[i - len];
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
V = N, E = M;
adj.resize(2*V);
iota(adj.begin(), adj.end(), 0);
revAdj.resize(2*V);
deg.assign(V, 0);
for (int i = 0; i < E; i++) {
int a = R[i][0], b = R[i][1];
if (deg[a] > deg[b]) {
swap(a, b);
}
assert(deg[a] <= deg[b]);
if (deg[a] == 0 && deg[b] == 0) {
adj[a] = b+V;
adj[b] = a+V;
adj[a+V] = b+V;
adj[b+V] = a+V;
}
else if (deg[a] == 0 && deg[b] >= 1) {
adj[a] = b;
adj[a+V] = b;
if (deg[b] == 1) {
adj[b+V] = a+V;
}
}
else if (deg[a] == 1) {
adj[a+V] = b;
if (deg[b] == 1) {
adj[b+V] = a;
}
}
deg[a]++, deg[b]++;
}
for (int i = 0; i < 2*V; i++) {
revAdj[adj[i]].push_back(i);
}
BFS(distP, P);
BFS(distPV, P+V);
// for (int i = 0; i < 2*V; i++) cerr << distPV[i] << " ";
// cerr << "\n";
cycleLen.assign(2*V, 0);
enum State{UNVISITED, VISITING, VISITED};
vector<State> state(2*V, UNVISITED);
for (int i = 0; i < 2*V; i++) {
if (state[i] == UNVISITED) {
int on = i;
vector<int> visiting;
while (state[on] == UNVISITED) {
// cerr << on << " ";
visiting.push_back(on);
state[on] = VISITING;
on = adj[on];
}
// cerr << "|" << on << "|\n";
if (state[on] == VISITING) {
int len = 1, j = (int)visiting.size()-1;
while (visiting[j] != on) {
j--, len++;
}
while (visiting.back() != on) {
cycleLen[visiting.back()] = len;
state[visiting.back()] = VISITED;
visiting.pop_back();
}
cycleLen[on] = len;
assert(visiting.back() == on);
while (!visiting.empty()) {
state[visiting.back()] = VISITED;
visiting.pop_back();
}
}
else {
assert(state[on] == VISITED);
for (int val : visiting) {
state[val] = VISITED;
}
visiting.clear();
}
}
}
// for (int i = 0; i < 2*V; i++) cerr << cycleLen[i] << " ";
// cerr << "\n";
makePref(distP, prefModP, cycleLen[P]);
makePref(distPV, prefModPV, cycleLen[P+V]);
for (int iq = 0; iq < Q; iq++) {
int ans = 0;
if (cycleLen[P] == 0 && G[iq] < 2*V) {
ans = prefModP[G[iq]] + prefModPV[G[iq]];
}
else {
int cP = cycleLen[P];
if (cP != 0) {
ans += prefModP[((2*V)/cP)*cP - 1];
}
int cPV = cycleLen[P+V];
if (cPV != 0) {
ans += prefModPV[((2*V)/cPV)*cPV - 1];
}
}
answer(ans);
}
}
