#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int MX = 3e5 + 5;
int n,m,q,p,k[MX],dist[MX],ans[MX], in_cycle, cycle_l,best[MX], s_best[MX],ans1[MX];
vector <int> v[MX], vr[MX],n_g[MX];
vector <pii> g[MX];
int can(int i) {
return 2 * i - 1;
}
int cnnt(int i) {
return 2 * i;
}
void bfs(int a) {
queue <int> q;
int pp = a;
for (int i = 1; i <= 2 * n; i++) {
dist[i] = -1;
}
q.push(a); dist[a] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int to : vr[x]) {
if (to == pp) {
in_cycle = 1;
cycle_l = dist[x] + 1;
}
if (dist[to] == -1) {
dist[to] = dist[x] + 1;
q.push(to);
}
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N; m = M; p = P; p++; q = Q;
for (int i = 1; i <= m; i++) {
int a, b;
a = R[i - 1][0]; b = R[i - 1][1];
a++; b++;
g[a].pb({i - 1, b});
g[b].pb({i - 1, a});
}
for (int i = 1; i <= q; i++) {
k[i] = G[i - 1];
}
for (int i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end());
best[i] = g[i][0].s;
s_best[i] = ((int)g[i].size() == 1 ? g[i][0].s : g[i][1].s);
}
for (int i = 1; i <= n; i++) {
int a = i, b = best[i];
if (best[b] == a) n_g[can(a)].pb(cnnt(b));
else n_g[can(a)].pb(can(b));
b = s_best[i];
if (best[b] == a) n_g[cnnt(a)].pb(cnnt(b));
else n_g[cnnt(a)].pb(can(b));
}
for (int i = 1; i <= n; i++) {
v[i].clear();
}
for (int i = 1; i <= 2 * n; i++) {
for (int x : n_g[i]) {
// cout<<i<<" -- "<<x<<"\n";
v[i].pb(x); vr[x].pb(i);
}
}
bfs(can(p));
for (int i = 1; i <= n; i++) {
if (dist[can(i)] == -1) continue;
ans[dist[can(i)]]++;
}
int fin = in_cycle, fl = cycle_l;
/* if (in_cycle) {
for (int i = cycle_l; i < MX; i++) {
ans[i] += ans[i - cycle_l];
}
}*/
in_cycle = 0;
bfs(cnnt(p));
int c_in = in_cycle, sl = cycle_l;
for (int i = 1; i <= n; i++) {
if (dist[can(i)] == -1) continue;
ans1[dist[can(i)]]++;
}
/* if(in_cycle) {
for (int i = cycle_l; i < MX; i++) {
ans1[i] += ans1[i - cycle_l];
}
}*/
n *= 2;
for(int i = 1; i <= q; i++) {
int res = 0;
int x = (fin ? (k[i] % fl) : 0), y = (c_in ? (k[i] % sl) : 0);
if (k[i] <= n) res += ans[k[i]], res += ans1[k[i]];
if (fin) {
for (int j = x; j <= min(k[i], n); j += fl) {
if (j == k[i]) continue;
res += ans[j];
}
}
if (c_in) {
for (int j = y; j <= min(k[i], n); j += sl) {
if (j == k[i]) continue;
res += ans1[j];
}
}
answer(res);
}
}
