#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>> g(N);
for(int i = 0;i<M;i++){
g[R[i][0]].push_back(R[i][1]);
g[R[i][1]].push_back(R[i][0]);
}
vector<int>mx(N);
for(int i = 0;i<N;i++){
mx[i] = g[i][0];
}
const int inf = 1e9 + 7;
vector<int>next(N * 2), vis(N * 2), pr(N * 2);
vector<vector<int>> rw( N * 2);
vector<array<int,2>> dist(N * 2, {inf, inf});
for(int i = 0;i<N;i++){
if(mx[g[i][0]] == i)next[i] = N + g[i][0];
else next[i] = g[i][0];
if(g[i].size() == 1){
next[N + i] = next[i];
}
else{
if(mx[g[i][1]] == i)next[N + i] = N + g[i][1];
else next[N + i] = g[i][1];
}
rw[next[i]].push_back(i);
rw[next[N+i]].push_back(N+i);
}
vector<vector<int>>cycle(2);
bool flag = false, flag2 = false;
auto dfs = [&](auto self, int x, int type) -> void {
vis[x] = 1;
int to = next[x];
if(vis[to] == 1){
int u = x;
while(u != to){
cycle[type].push_back(u);
u = pr[u];
}
cycle[type].push_back(to);
return;
}
else{
vis[to] = 1;
pr[to] = x;
self(self, to, type);
}
};
dfs(dfs, P, 0);
for(int i = 0;i<N*2;i++)vis[i] = 0;
dfs(dfs, P + N, 1);
reverse(cycle[0].begin(), cycle[0].end());
reverse(cycle[1].begin(), cycle[1].end());
auto que = [&](int x, int type) -> void {
dist[x][type] = 0;
queue<int>q;
q.push(x);
while(!q.empty()){
auto i = q.front();
q.pop();
for(auto to : rw[i]){
if(dist[to][type] > dist[i][type] + 1){
dist[to][type] = dist[i][type] + 1;
q.push(to);
}
}
}
};
que(P, 0);
que(N + P, 1);
int sz1 = cycle[0].size();
int sz2 = cycle[1].size();
for(auto to : cycle[0])if(to == P)flag = true;
for(auto to : cycle[1])if(to == N + P)flag2 = true;
vector<array<int,3>>v;
vector<array<int,2>> qs;
vector<int>res(Q);
vector<array<int,3>>cnt(N*2);
vector<map<int,int>>op(2);
for(int i = 0;i<N;i++){
v.push_back({dist[i][0], 0, sz1});
v.push_back({dist[i][1], 1, sz2});
}
for(int i = 0;i<Q;i++){
qs.push_back({G[i], i});
}
sort(qs.begin(), qs.end());
sort(v.begin(), v.end());
int l = 0;
for(auto [val, ind] : qs){
while(l < v.size() && v[l][0] <= val){
cnt[v[l][0] % v[l][2]][v[l][1]] += 1;
op[v[l][1]][v[l][0]] += 1;
l += 1;
}
if(!flag){
res[ind] += op[0][val];
}
else res[ind] += cnt[val % sz1][0];
if(!flag2){
res[ind] += op[1][val];
}
else res[ind] += cnt[val % sz2][1];
}
for(auto to : res)answer(to);
}
