#include <bits/stdc++.h>
#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 <vector<pair<int,int>>> res(N);
for (int i = 0; i < M; i++) {
int u = R[i][0];
int v = R[i][1];
res[v].emplace_back(i,u);
res[u].emplace_back(i,v);
}
for (int i = 0; i < N; i++) {
sort(res[i].begin(),res[i].end());
}
int to[2*N];
for (int i = 0; i < N; i++) {
int best = res[i][0].second;
int scbest = (res[i].size() > 1) ? res[i][1].second : best;
if (res[best][0].second == i) {
to[i] = best + N;
} else {
to[i] = best;
}
if (res[scbest][0].second == i) {
to[i+N] = scbest + N;
} else {
to[i+N] = scbest;
}
}
int clen = 0;
int used[2*N] = {};
int cur = P;
used[cur] = 1;
int cnt = 1;
while (!used[to[cur]]) {
cur = to[cur];
cnt++;
}
if (to[cur] == P) clen = cnt;
vector <vector<int>> v(2*N);
for (int i = 0; i < 2*N; i++) {
v[to[i]].emplace_back(i);
}
queue <int> q;
q.push(P);
int d[2*N];
for (int i = 0; i < 2*N; i++) d[i] = INT_MAX;
d[P] = 0;
while (!q.empty()) {
int f = q.front();
q.pop();
for (auto to:v[f]) {
if (d[to] > d[f] + 1) {
d[to] = d[f] + 1;
q.push(to);
}
}
}
bool ok[2*N];
for (int q = 0; q < Q; q++) {
int k = G[q];
for (int i = 0; i < 2*N; i++) {
if (clen == 0) {
ok[i] = (k == d[i]);
continue;
}
ok[i] = ((d[i]-k)%clen == 0);
}
int ans = 0;
for (int i = 0; i < 2*N; i++) {
ans += ok[i];
}
answer(ans);
}
}
