#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
#define pr pair<int, int>
#define pb push_back
using namespace std;
const ll INF = 1e18+1, MOD = 1e9+7;
vector<vector<int>> edge;
vector<vector<pr>> dist; // dist from the node to the p, first path used or not (1 for used, 0 for not)
vector<vector<bool>> vis, badvis;
int p;
pr find(int node, int prev) {
if (node == p) {
if (edge[node][0] == prev) return {0, 1}; // went to the p using the beautiful path
else return {0, 0}; // went to the p without using the first path, thus
}
pr res;
int used = (edge[node][0] == prev);
if (vis[node][used] || badvis[node][used]) {
badvis[node][used] = 1;
return {-1, -1}; // useless loop
}
vis[node][used] = 1;
if (dist[node][used].first != -1) {
vis[node][used] = 0;
return dist[node][used];
}
else {
if (used && edge[node].size() > 1) {
res = find(edge[node][1], node);
}
else {
res = find(edge[node][0], node);
}
}
if (res == make_pair(-1, -1)) {
vis[node][used] = 0;
badvis[node][used] = 1;
return dist[node][used] = {-1, -1};
}
vis[node][used] = 0;
return dist[node][used] = {res.first+1, res.second};
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
p = P;
vector<int> ans(Q, 0);
edge.assign(N, vector<int>());
dist.assign(N, vector<pr>(2, {-1, -1}));
vis.assign(N, vector<bool>(2, 0));
badvis.assign(N, vector<bool>(2, 0));
for (int i = 0; i < M; i++) {
edge[R[i][0]].pb(R[i][1]);
edge[R[i][1]].pb(R[i][0]);
}
for (int i = 0; i < N; i++) {
// vis.assign(N, vector<bool>(2, 0));
if (dist[i][0].first == -1) {
find(i, -1);
}
// vis.assign(N, vector<bool>(2, 0));
if (dist[i][1].first == -1) {
find(i, edge[i][0]);
}
}
pr temp1 = find(edge[p][0], p);
pr temp2 = find(((edge[p].size() > 1) ? edge[p][1] : edge[p][0]), p);
dist[p][0] = {temp1.first + 1, temp1.second}; // from state 0, go to edge[p][1]
dist[p][1] = {temp2.first + 1, temp2.second}; // from state 1, go to edge[p][0]
int cycle[2];
cycle[0] = dist[p][0].first;
cycle[1] = dist[p][1].first;
if (cycle[0] == 0) cycle[0] = -1;
if (cycle[1] == 0) cycle[1] = -1;
int next[2];
next[0] = dist[p][0].second;
next[1] = dist[p][1].second;
for (int i = 0; i < Q; i++) {
int res = 0;
for (int j = 0; j < N; j++) {
int k = G[i];
if (dist[j][0].first == -1) continue;
k -= dist[j][0].first;
if (k < 0) continue;
if (k == 0) {res++; continue;}
int used = dist[j][0].second;
if (cycle[used] == -1) continue;
k -= cycle[used];
used = next[used];
if (k == 0) {res++; continue;}
if (k < 0) continue;
if (next[used] == used && cycle[used] > 0) {
if (next[used] == -1) continue;
k %= cycle[used];
}
else {
if (cycle[0] == -1 || cycle[1] == -1) continue;
k %= (cycle[0] + cycle[1]);
if (k > 0) k -= cycle[used];
}
if (k == 0) res++;
}
ans[i] = res;
}
for(int i=0; i<Q; i++)
answer(ans[i]);
}
