#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int T, st[N], ed[N], h[N], in[N];
int e[N], nxt[N], par[N], deg[N], pos[N];
vector<int> vec[N], cir[N], G[N];
int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
void join(int u, int v) { par[find(u)] = find(v); }
void dfs(int u, int r) {
st[u] = ++T, in[u] = r;
for (auto v : G[u]) {
if (deg[v]) continue;
h[v] = h[u] + 1, dfs(v, r);
}
ed[u] = ++T;
}
void solve(int root) {
if (vec[root].size() == 1) return;
for (auto i : vec[root]) {
deg[nxt[i]]++, G[nxt[i]].push_back(i);
}
queue<int> qu;
for (auto i : vec[root]) if (!deg[i]) qu.push(i);
while (qu.size()) {
int u = qu.front(); qu.pop();
deg[nxt[u]]--;
if (!deg[nxt[u]]) qu.push(nxt[u]);
}
for (auto i : vec[root]) {
if (!deg[i]) continue;
int cur = i;
while (1) {
pos[cur] = cir[root].size();
cir[root].push_back(cur);
cur = nxt[cur];
if (cur == i) break;
}
break;
}
for (auto i : cir[root]) dfs(i, i);
}
void count_routes(int n, int m, int p, int R[][2], int q, int X[]) {
if (n > 1000) return;
for (int i = 0; i < n * 2; ++i) e[i] = nxt[i] = -1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 2; ++j) {
int u = R[i][j];
if (e[u] == -1) e[u] = i;
else if (e[u + n] == -1) e[u + n] = i;
}
}
for (int i = 0; i < n; ++i) {
int j;
j = R[e[i]][0] + R[e[i]][1] - i;
if (e[j] == e[i]) {
if (e[j + n] == -1) nxt[i] = j;
else nxt[i] = j + n;
}
else nxt[i] = j;
if (e[i + n] != -1) {
j = R[e[i + n]][0] + R[e[i + n]][1] - i;
if (e[j] == e[i + n]) {
if (e[j + n] == -1) nxt[i + n] = j;
else nxt[i + n] = j + n;
}
else nxt[i + n] = j;
}
}
for (int i = 0; i < n * 2; ++i) par[i] = i;
for (int i = 0; i < n * 2; ++i) if (nxt[i] != -1) join(i, nxt[i]);
for (int i = 0; i < n * 2; ++i) vec[find(i)].push_back(i);
for (int i = 0; i < n * 2; ++i) if (par[i] == i) solve(i);
// for (int i = 0; i < n * 2; ++i) cout << nxt[i] << ' '; cout << '\n';
for (int i = 0; i < q; ++i) {
int res = 0;
for (int j = 0; j < n; ++j) {
int cur = j, tmp = X[i];
while (tmp--) cur = nxt[cur];
if (cur == p || cur == p + n) res++;
// if (h[j] >= X[i]) {
// if (par[j] == par[p] && st[p] <= st[j] && ed[j] <= ed[p] && h[j] - h[p] == X[i]) ++res;
// else if (par[j] == par[p + n] && st[p + n] <= st[j] && ed[j] <= ed[p + n] && h[j] - h[p + n] == X[i]) ++res;
// }
// else {
// int tmp = cir[par[j]][(pos[in[j]] + X[i] - h[j]) % cir[par[j]].size()];
// if (tmp == p || tmp == p + n) res++;
// }
}
answer(res);
}
}
