#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
constexpr int maxn = 2 * 110000 + 10;
vector<int> grafo[maxn];
int n, m, f[maxn][2], x[maxn];
int p, k;
bool mark[maxn];
stack<int> st, cycle;
vector<int> mod[maxn][2];
int eh_ciclo[2];
inline void build_reverse_graph() {
for (int i = 0; i < 2*n; i++)
grafo[ x[i] ].push_back(i);
}
bool dfs(int u, int aux) {
mark[u] = 1;
st.push(u);
int v = x[u];
if (v == aux) {
while (!st.empty() && st.top() != aux) {
cycle.push(st.top());
st.pop();
}
if (!st.empty()) cycle.push(st.top()), st.pop();
return true;
}
if (mark[v])
return false;
return dfs(v, aux);
}
int check_cycle(int p) {
while (!st.empty()) st.pop();
while (!cycle.empty()) cycle.pop();
for (int i = 0; i < 2*n; i++)
mark[i] = 0;
return (dfs(p, p) ? cycle.size() : 0);
}
map<int, int> ans[2];
int dist[maxn];
void bfs(int u) {
for (int i = 0; i < 2*n; i++)
dist[i] = 0x3f3f3f3f, mark[i] = 0;
queue<int> fila;
fila.push(u);
dist[u] = 0;
while (!fila.empty()) {
int u = fila.front();
fila.pop();
if (mark[u]) continue;
mark[u] = true;
if (u < n)
ans[k][ dist[u] ]++;
for (auto v : grafo[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
fila.push(v);
}
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
memset(f, -1, sizeof f);
n = N, m = M;
p = P;
for (int i = 0; i < m; i++) {
int a, b;
a = R[i][0], b = R[i][1];
if (f[a][0] == -1) f[a][0] = b;
else if (f[a][1] == -1) f[a][1] = b;
if (f[b][0] == -1) f[b][0] = a;
else if (f[b][1] == -1) f[b][1] = a;
}
for (int u = 0; u < n; u++) {
if (f[u][1] == -1) f[u][1] = f[u][0];
int v = f[u][0];
if (f[v][0] == u)
x[u] = v+n;
else
x[u] = v;
}
for (int u = n; u < 2*n; u++) {
int u_ = u - n;
int v = f[u_][1];
if (f[v][0] == u_)
x[u] = v+n;
else
x[u] = v;
}
//for (int i = 0; i < 2*n; i++)
//cout << (i < n ? i : i-n) << (i < n ? " " : "' ") << (x[i] < n ? x[i] : x[i]-n)
//<< (x[i] < n ? "\n" : "'\n");
build_reverse_graph();
eh_ciclo[0] = check_cycle(p);
eh_ciclo[1] = check_cycle(p+n);
bfs(p);
k++;
bfs(p+n);
for (int l = 0; l < 2; l++) {
if (eh_ciclo[l]) {
for (auto & e : ans[l])
mod[e.first%eh_ciclo[l]][l].push_back(e.first);
}
}
for (int i = 0 ; i < Q; i++) {
int g = G[i];
int resp = 0;
for (int l = 0; l < 2; l++) {
if (eh_ciclo[l]) {
for (auto& e : mod[g%eh_ciclo[l]][l])
if (g >= e) resp += ans[l][e];
} else
resp += ans[l][g];
}
answer(resp);
}
}
//int main() {
//return 0;
//}
