#include <iostream>
#include <queue>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int Sz = 3<<17, inf = 2e9;
vector<int> nei[Sz], rev[Sz];
int cyc[Sz], seen[Sz], Dfs[Sz], cur, Mn[2][Sz], lst[Sz], bst[Sz], sbst[Sz];
void dfs(int u){
seen[u] = 1;
if (Dfs[u])
cyc[u] = cur - lst[u];
lst[u] = cur++;
Dfs[u]++;
for (int i : nei[u]){
if (Dfs[i] == 2 or (Dfs[i] == 0 and seen[i] == 1))
continue;
dfs(i);
}
Dfs[u]--;
}
void bfs(int s, int id){
for (int i=0;i<Sz;i++)
Mn[id][i] = inf;
Mn[id][s] = 0;
queue<int> Q; Q.push(s);
while (Q.size() > 0){
s = Q.front();
Q.pop();
for (int i : rev[s]){
if (Mn[id][i] > Mn[id][s] + 1)
Mn[id][i] = Mn[id][s] + 1, Q.push(i);
}
}
}
void count_routes(int n, int m, int p, int R[][2], int q, int g[]){
for (int i=0;i<n;i++)
bst[i] = Sz;
for (int i=m-1;i>=0;i--){
int a = R[i][0], b = R[i][1];
sbst[a] = bst[a], bst[a] = i;
sbst[b] = bst[b], bst[b] = i;
}
for (int i=0;i<n;i++){
int K = 0;
if (sbst[i] == Sz)
sbst[i] = bst[i];
for (int e : {bst[i], sbst[i]}){
if (e == Sz)
continue;
int j = R[e][0] + R[e][1] - i;
if (bst[j] == e)
j += n;
nei[i+K].push_back(j);
rev[j].push_back(i+K);
K = n;
}
}
for (int i=0;i<n + n;i++){
if (seen[i] == 0)
dfs(i);
}
bfs(p, 0);
bfs(p + n, 1);
for (int j=0;j<q;j++){
int ans = 0, d = g[j];
for (int i=0;i<n;i++){
bool t = 0;
if (Mn[0][i] == d or Mn[1][i] == d)
ans++;
else if (Mn[0][i] <= d and cyc[p] != 0 and (d - Mn[0][i]) % cyc[p] == 0)
ans++;
else if (Mn[1][i] <= d and cyc[p+n] != 0 and (d - Mn[1][i]) % cyc[p + n] == 0)
ans++;
}
answer(ans);
}
}
