#include "garden.h"
#include "gardenlib.h"
#include <vector>
#define MAXN 150000
#define MAXK 300000
#define MAXQ 2000
int ans[MAXQ];
std::vector < int > g[MAXK + 1];
int muchie[MAXN][2], t[MAXK + 1];
int id[MAXN][2], h[MAXK + 1];
bool viz[MAXK + 1];
inline void avem(int x, int y) {
if (muchie[x][0] == -1)
muchie[x][0] = y;
else if (muchie[x][1] == -1)
muchie[x][1] = y;
}
inline void getPapa(int x, int r) {
if (muchie[muchie[x][r]][0] != x) {
t[id[x][r]] = id[muchie[x][r]][0];
g[t[id[x][r]]].push_back(id[x][r]);
} else {
t[id[x][r]] = id[muchie[x][r]][1];
g[t[id[x][r]]].push_back(id[x][r]);
}
}
void dfs(int x) {
viz[x] = 1;
for (auto &y : g[x]) {
if (viz[y] == 0) {
h[y] = h[x] + 1;
dfs(y);
}
}
}
inline void solve(int s, int n, int q, int k[], int N) {
for (int i = 1; i <= n; i++)
viz[i] = 0;
int x = s, cnt = 0;
while (viz[x] == 0) {
viz[x] = 1;
h[x] = 0;
cnt++;
x = t[x];
}
if (x == s) {
int len = cnt;
while (cnt > 0) {
cnt--;
x = t[x];
h[x] = cnt;
dfs(x);
}
for (int i = 0; i < q; i++)
for (int j = 0; j < N; j++)
if (viz[id[j][0]] && k[i] >= h[id[j][0]])
ans[i] += (k[i] - h[id[j][0]]) % len == 0;
} else {
dfs(s);
for (int i = 0; i < q; i++)
for (int j = 0; j < N; j++)
if (viz[id[j][0]] && h[id[j][0]])
ans[i] += k[i] == h[id[j][0]];
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
for (int i = 0; i < N; i++)
muchie[i][0] = muchie[i][1] = -1;
for (int i = 0; i < M; i++) {
int x = R[i][0], y = R[i][1];
avem(x, y);
avem(y, x);
}
int k = 0;
for (int i = 0; i < N; i++) {
id[i][0] = ++k;
if (muchie[i][1] == -1)
muchie[i][1] = muchie[i][0], id[i][1] = k;
else
id[i][1] = ++k;
}
for (int i = 1; i <= k; i++)
g[i].clear();
for (int i = 0; i < N; i++) {
getPapa(i, 0);
getPapa(i, 1);
}
for (int i = 0; i < Q; i++)
ans[i] = 0;
solve(id[P][0], k, Q, G, N);
if (id[P][1] != id[P][0])
solve(id[P][1], k, Q, G, N);
for (int i = 0; i < Q; i++)
answer(ans[i]);
}
