#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using ll = long long;
constexpr int INF = 1e9;
using namespace std;
void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
vector<vector<array<int, 2>>> grf(n);
for (int i = 0; i < m; i++)
{
grf[r[i][0]].push_back({r[i][1], i});
grf[r[i][1]].push_back({r[i][0], i});
}
vector<vector<array<int,2>>> rev(n);
for (int i = 0; i < n; i++)
{
if (grf[i].size() > 2)
grf[i].resize(2);
for (const auto &[j, w] : grf[i])
rev[j].push_back({i, w});
}
vector< array<int,2>> dist(n,{INF,INF});
vector< array<int,2>> dist2(n,{INF,INF});
for (int total = 0; total < 2; total++) {
if (total == 1 && grf[p].size() == 1)
break;
queue<array<int,3>> bfs;
bfs.push({0, p, total});
while (!bfs.empty())
{
const auto [t, u, f] = bfs.front();
bfs.pop();
if (dist[u][f]!=INF)
continue;
dist[u][f]=t;
int cum=grf[u][0][1];
for (const auto &[j, cioara] : rev[u])
{
if (f==0&&cioara==cum&&grf[u].size()>1)
continue;
if (f == 1&&cioara!=cum&&grf[u].size()>1)
continue;
int stegulet =(cioara!=grf[j][0][1]);
bfs.push({t + 1, j, stegulet});
}
}
for (int i = 0; i < n; i++)
dist2[i][total] = dist[i][0];
dist.assign(n, {INF, INF});
}
const auto get_cycle = [&](int f) -> array<int, 2>
{
int lll = 0;
int viz = 0;
vector<array<bool,2>> vis(n);
int node = p, stegulet = f, ll = 0;
while (!vis[node][stegulet])
{
vis[node][stegulet] = true;
if (node == p && stegulet == !f)
viz = ll;
const auto [urm,cum] = grf[node][stegulet];
if (grf[urm].size() == 1)
node = urm, stegulet = 0;
else{
node=urm;
stegulet=(grf[urm][0][1]==cum);
}
ll++;
}
if (node == p)
lll=ll;
else
{
lll = INT_MAX;
viz = 0;
}
return {lll, viz};
};
array<int,2> v1=get_cycle(0);
array<int,2> v2={INT_MAX, 0};
if (grf[p].size() > 1)
v2 = get_cycle(1);
for (int j=0;j<q;j++)
{
int k = g[j],cnt=0;
for (int i = 0; i < n; i++)
{
if (dist2[i][0]<=k&&((k-dist2[i][0])%v1[0]==0||(k-dist2[i][0])%v1[0]==v1[1]))
cnt++;
else if (dist2[i][1]<=k&&((k-dist2[i][1])%v2[0]==0||(k-dist2[i][1])%v2[0]==v2[1]))
cnt++;
}
answer(cnt);
}
}
