#include "gardenlib.h"
#include "garden.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 150000;
int best[MAXN], best2[MAXN], nxt[2 * MAXN], ans[2 * MAXN + 1], viz[2 * MAXN], ciclu[2 * MAXN], oncycle[2 * MAXN];
int depth[2 * MAXN], tin[2 * MAXN], tout[2 * MAXN], timer, root[2 * MAXN], cyclepoz[2 * MAXN], cyclesz[2 * MAXN];
int ord[MAXN], answers[MAXN], freq[2][2 * MAXN + 1];
vector<int> g[2 * MAXN], upd[2];
void dfs(int node) {
tin[node] = ++timer;
for(int son : g[node]) {
depth[son] = 1 + depth[node];
root[son] = root[node];
dfs(son);
}
tout[node] = timer;
}
void solve(int node, int target, int which) {
if(ciclu[node] != ciclu[target]) {
return;
}
if(!oncycle[target]) {
if(tin[target] <= tin[node] && tout[node] <= tout[target]) {
ans[depth[node] - depth[target]]++;
}
return;
}
int cnt = depth[node];
node = root[node];
if(cyclepoz[node] <= cyclepoz[target]) {
cnt += cyclepoz[target] - cyclepoz[node];
} else {
cnt += cyclesz[ciclu[node]] - cyclepoz[node] + cyclepoz[target];
}
upd[which].push_back(cnt);
}
void count_routes(int n, int m, int p, int r[][2], int q, int qval[]) {
for(int i = 0; i < n; i++) {
best[i] = best2[i] = -1;
}
for(int i = m - 1; i >= 0; i--) {
best2[r[i][0]] = best[r[i][0]];
best[r[i][0]] = r[i][1];
best2[r[i][1]] = best[r[i][1]];
best[r[i][1]] = r[i][0];
}
for(int i = 0; i < n; i++) {
if(best2[i] == -1) {
best2[i] = best[i];
}
}
for(int i = 0; i < n; i++) {
nxt[2 * i] = 2 * best[i] + (best[best[i]] == i);
nxt[2 * i + 1] = 2 * best2[i] + (best[best2[i]] == i);
}
int nrciclu = 0;
for(int i = 0; i < 2 * n; i++) {
if(!viz[i]) {
int j = i;
while(!viz[j]) {
viz[j] = 1;
j = nxt[j];
}
if(ciclu[j] == 0) {
int q = j, poz = 0;
ciclu[j] = ++nrciclu;
oncycle[j] = 1;
cyclepoz[j] = ++poz;
while(nxt[q] != j) {
q = nxt[q];
ciclu[q] = nrciclu;
oncycle[q] = 1;
cyclepoz[q] = ++poz;
}
cyclesz[nrciclu] = poz;
}
int q = i;
while(q != j) {
ciclu[q] = ciclu[j];
q = nxt[q];
}
}
}
for(int i = 0; i < 2 * n; i++) {
if(!oncycle[i]) {
g[nxt[i]].push_back(i);
}
}
for(int i = 0; i < 2 * n; i++) {
if(oncycle[i]) {
root[i] = i;
dfs(i);
}
}
for(int i = 0; i < n; i++) {
solve(2 * i, 2 * p, 0);
solve(2 * i, 2 * p + 1, 1);
}
sort(upd[0].begin(), upd[0].end());
sort(upd[1].begin(), upd[1].end());
for(int i = 0; i < q; i++) {
ord[i] = i;
}
sort(ord, ord + q, [&](int a, int b) {
return qval[a] < qval[b];
});
int ptr[2] = {0, 0}, sizes[2] = {cyclesz[ciclu[2 * p]], cyclesz[ciclu[2 * p + 1]]};
for(int i = 0; i < q; i++) {
while(ptr[0] < (int)upd[0].size() && upd[0][ptr[0]] <= qval[ord[i]]) {
freq[0][upd[0][ptr[0]++] % sizes[0]]++;
}
while(ptr[1] < (int)upd[1].size() && upd[1][ptr[1]] <= qval[ord[i]]) {
freq[1][upd[1][ptr[1]++] % sizes[1]]++;
}
answers[ord[i]] = freq[0][qval[ord[i]] % sizes[0]] + freq[1][qval[ord[i]] % sizes[1]];
if(qval[ord[i]] <= 2 * n) {
answers[ord[i]] += ans[qval[ord[i]]];
}
}
for(int i = 0; i < q; i++) {
answer(answers[i]);
}
}
