#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
int i, t;
};
struct Req {
bool add;
int t, k, id;
};
const int N = 3e5 + 42, Q = 2e3 + 10, INF = 2e9;
bool b[N][2];
Node nex[N][2];
vector<int> adj[N];
vector<Node> pre[N][2];
int n, m, fin, q, step[Q], occ[N][2], arc[N], cycle[2], dist[N][2][2], ans[N];
void BFS(int k) {
queue<Node> q;
q.push({fin, k});
dist[fin][k][k] = 0;
while(!q.empty()) {
Node act = q.front();
q.pop();
for(Node next : pre[act.i][act.t]) {
if(dist[next.i][next.t][k] == INF) {
dist[next.i][next.t][k] = dist[act.i][act.t][k] + 1;
q.push(next);
}
}
}
}
void count_routes(int N_, int M_, int P_, int R[][2], int Q_, int G[]) {
n = N_, m = M_, fin = P_, q = Q_;
for(int i = 0; i < m; i++)
arc[i] = R[i][0] + R[i][1];
for(int i = 0; i < m; i++) {
if(adj[R[i][0]].size() < 2) {
adj[R[i][0]].push_back(i);
}
if(adj[R[i][1]].size() < 2) {
adj[R[i][1]].push_back(i);
}
}
for(int i = 0; i < n; i++)
if(adj[i].size() == 1)
adj[i].push_back(adj[i][0]);
for(int i = 0; i < n; i++)
for(int j = 0; j < 2; j++) {
int s = arc[adj[i][j]] - i;
if(adj[i][j] == adj[s][0]) {
nex[i][j] = {s, 1};
pre[s][1].push_back({i, j});
} else {
nex[i][j] = {s, 0};
pre[s][0].push_back({i, j});
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
dist[i][j][k] = INF;
int i = fin, j = 0, nb = 0;
cycle[0] = cycle[1] = -1;
do {
nb++;
b[i][j] = true;
Node next = nex[i][j];
i = next.i;
j = next.t;
} while(!b[i][j]);
if(i == fin && j == 0) {
cycle[0] = nb;
}
for(int i = 0; i < n; i++)
b[i][0] = b[i][1] = false;
i = fin, j = 1, nb = 0;
do {
nb++;
b[i][j] = true;
Node next = nex[i][j];
i = next.i;
j = next.t;
} while(!b[i][j]);
if(i == fin && j == 1) {
cycle[1] = nb;
}
BFS(0);
BFS(1);
vector<Req> req;
for(int i = 0; i < n; i++)
for(int k = 0; k < 2; k++)
if(dist[i][0][k] != INF)
req.push_back({true, dist[i][0][k], k, 0});
for(int i = 0; i < q; i++)
req.push_back({false, G[i], 0, i});
sort(req.begin(), req.end(),
[](Req a, Req b) {
if(a.t == b.t)
return a.add;
return a.t < b.t;
});
for(Req r : req) {
if(r.add) {
if(cycle[r.k] == -1) {
occ[r.t][r.k]++;
} else {
occ[r.t % cycle[r.k]][r.k]++;
}
} else {
if(cycle[0] == -1) {
if(r.id < N)
ans[r.id] += occ[r.t][0];
} else {
ans[r.id] += occ[r.t % cycle[0]][0];
}
if(cycle[1] == -1) {
if(r.id < N)
ans[r.id] += occ[r.t][1];
} else {
ans[r.id] += occ[r.t % cycle[1]][1];
}
}
}
for(int i = 0; i < q; i++)
answer(ans[i]);
}
