#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
struct Edge {
int idx, to;
Edge(int a = 0, int b = 0) : idx(a), to(b) {}
bool operator < (const Edge& a) const {
return (idx < a.idx);
}
};
const int MAXN = 150010;
const int INF = 0x3f3f3f3f;
const int MAXLOG = 30;
int n, m, p;
vector<Edge> adj1[MAXN];
pii nxt[MAXN][2];
pii binl[30][MAXN][2];
int mi[MAXN];
vector<pii> adj[MAXN][2];
int dist[2][MAXN][2];
int vis[MAXN][2];
// first is tam, second is if its included
pii pV[2];
int qtd[MAXN];
int qtdM[MAXN];
void init(int q) {
memset(vis, 0, sizeof vis);
pii curr = {p, q};
while (vis[curr.fr][curr.se] != 2) {
vis[curr.fr][curr.se]++;
curr = nxt[curr.fr][curr.se];
}
if (vis[p][q] == 2) {
pV[q].se = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) if (vis[i][j]) pV[q].fr++;
}
}
void count_routes(int32_t N, int32_t M, int32_t P, int32_t R[][2], int32_t Q, int32_t G[])
{
n = N;
m = M;
p = P;
for (int i = 0; i < n; i++) {
mi[i] = INF;
dist[0][i][0] = dist[0][i][1] = INF;
dist[1][i][0] = dist[1][i][1] = INF;
}
for (int i = 0; i < m; i++) {
int a = R[i][0], b = R[i][1];
adj1[a].push_back(Edge(i, b));
adj1[b].push_back(Edge(i, a));
mi[a] = min(mi[a], i);
mi[b] = min(mi[b], i);
}
for (int i = 0; i < n; i++) {
sort(adj1[i].begin(), adj1[i].end());
}
for (int i = 0; i < n; i++) {
// faz o do 0
bool f = 0;
if (mi[adj1[i][0].to] == adj1[i][0].idx) f = 1;
nxt[i][0] = make_pair(adj1[i][0].to, f);
// faz o do 1
if (((int) adj1[i].size()) == 1) {
nxt[i][1] = nxt[i][0];
} else {
f = 0;
if (mi[adj1[i][1].to] == adj1[i][1].idx) f = 1;
nxt[i][1] = make_pair(adj1[i][1].to, f);
}
}
// fazer nova adj
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
pii a = nxt[i][j];
adj[a.fr][a.se].push_back({i, j});
}
}
// calcular a distância de todo mundo até o p
for (int b = 0; b < 2; b++) {
dist[b][p][b] = 0;
queue<pii> q;
q.push({p, b});
while (!q.empty()) {
auto u = q.front();
q.pop();
for (auto v : adj[u.fr][u.se]) {
if (dist[b][v.fr][v.se] != INF) continue;
dist[b][v.fr][v.se] = (dist[b][u.fr][u.se] + 1);
q.push(v);
}
}
}
// tá legal, agora sei a distância de todo mundo
init(0);
init(1);
vector<int> ans(Q);
vector<pii> queries;
for (int i = 0; i < Q; i++) {
queries.push_back({G[i], i});
}
sort(queries.begin(), queries.end());
// calcular resposta pro p[0]
for (int b = 0; b < 2; b++) {
memset(qtd, 0, sizeof qtd);
memset(qtdM, 0, sizeof qtdM);
vector<int> c;
for (int i = 0; i < n; i++) {
c.push_back(dist[b][i][0]);
}
sort(c.begin(), c.end());
int curr = 0;
for (int i = 0; i < Q; i++) {
while ((curr < ((int)c.size())) && (c[curr] <= queries[i].fr)) {
if (c[curr] < MAXN) qtd[c[curr]]++;
qtdM[c[curr] % pV[b].fr]++;
curr++;
}
if (pV[b].se) {
// tá no ciclo
ans[queries[i].se] += qtdM[queries[i].fr % pV[b].fr];
} else {
if (queries[i].fr < MAXN) ans[queries[i].se] += qtd[queries[i].fr];
}
}
}
for (auto u : ans) answer(u);
}
