#include <bits/stdc++.h>
#include <vector>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
vector<int> ans(Q);
vector<vector<int>> g(N, vector<int>(0));
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<vector<int>> DP(N, vector<int>(2, -1));
int timer = -1;
int cycSz = -1;
auto dfs = [&](auto self, int node, int prevNode) -> void
{
timer++;
int state = 0, nextNode = g[node][0];
if (g[node][0] == prevNode && g[node].size() >= 2)
{
state = 1;
nextNode = g[node][1];
}
if (DP[node][state] != -1)
{
if (node == P) cycSz = timer-DP[node][state];
return;
}
DP[node][state] = timer;
self(self, nextNode, node);
return;
};
dfs(dfs, P, (g[P].size()>1?-1:g[P][0]));
DP.clear();
DP.resize(N, vector<int>(2, -2));
DP[P][0] = 0;
auto prop = [&](auto self, int node, int prevNode) -> int {
int state = 0, nextNode = g[node][0];
if (g[node][0] == prevNode && g[node].size() >= 2)
{
state = 1;
nextNode = g[node][1];
}
if (DP[node][state] != -2) return DP[node][state];
DP[node][state] = -1;
int step = self(self, nextNode, node);
if (step != -1) step++;
DP[node][state] = step;
return DP[node][state];
};
for (int i = 0; i < N; i++) prop(prop, i, -1);
int cnt = 0;
// auto dfs2 = [&](auto self, int node, int prevNode, int K) -> void
// {
// int state = 0;
// if (g[node][0] != prevNode) state = 1;
// if (state == 0 && DP[node][state] != -1) {
// if (DP[node][state] == K || (cycSz != -1 && K > DP[node][state] && (K-DP[node][state])%cycSz == 0)) cnt++;
// }
// // cout << "node " << node << " " << state << '\n';
// if (vis[node][state] != -1) return;
// vis[node][state] = 1;
// if (state == 0) {
// for (int i = 1; i < g[node].size(); i++) self(self, g[node][i], node, K);
// } else self(self, g[node][0], node, K);
// return;
// };
for (int i = 0; i < Q; i++) {
cnt = 0;
// vis.clear();
// vis.resize(N, vector<int>(2, -1));
// dfs2(dfs2, P, g[P][0], G[i]);
for (int j = 0; j < N; j++) {
if (DP[j][0] == G[i] || (DP[j][0] != -1 && cycSz != -1 && G[i] > DP[j][0] && (G[i]-DP[j][0])%cycSz == 0)) cnt++;
}
ans[i] += cnt;
}
if (g[P].size() > 1) {
DP.clear();
DP.resize(N, vector<int>(2, -1));
timer = 1; cycSz = -1;
dfs(dfs, P, g[P][0]);
DP.clear();
DP.resize(N, vector<int>(2, -2));
DP[P][1] = 0;
for (int i = 0; i < N; i++) {
prop(prop, i, -1);
}
for (int i = 0; i < Q; i++) {
cnt = 0;
// vis.clear();
// vis.resize(N, vector<int>(2, -1));
// dfs2(dfs2, P, -1, G[i]);
for (int j = 0; j < N; j++) {
if (DP[j][0] == G[i] || ( DP[j][0] != -1 && cycSz != -1 && G[i] > DP[j][0] && (G[i]-DP[j][0])%cycSz == 0)) cnt++;
}
ans[i] += cnt;
}
}
for (int i = 0; i < Q; i++) answer(ans[i]);
}
