/* https://oj.uz/submission/246701 (rqi) */
#include "garden.h"
#include "gardenlib.h"
#include <string.h>
#include <stdlib.h>
#define N 150000
#define Q 2000
#define INF 0x3f3f3f3f
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *ej[N * 2], eo[N * 2], n;
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int rr[N * 2], xx[N * 2], yy[N * 2], cc[N * 2], ta[N * 2], tb[N * 2], r, c; char state[N * 2];
void dfs(int i, int x, int y) {
static int time;
int o;
if (state[i] == -2)
state[i] = 2, x = 0;
else
state[i] = 1;
rr[i] = r, xx[i] = x, yy[i] = y % c, cc[i] = c, ta[i] = time++;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (state[j] <= 0)
dfs(j, x + 1, y + 1);
}
tb[i] = time;
}
int compare_xt(int i, int j) {
return xx[i] != xx[j] ? xx[i] - xx[j] : ta[i] - ta[j];
}
int compare_ryx(int i, int j) {
return rr[i] != rr[j] ? rr[i] - rr[j] : (yy[i] != yy[j] ? yy[i] - yy[j] : xx[i] - xx[j]);
}
void sort(int *ii, int l, int r, int (*compare)(int, int)) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i, compare);
l = k;
}
}
int ii[N], jj[N];
int search1(int x, int t) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int h = (lower + upper) / 2, i = ii[h];
if (xx[i] < x || xx[i] == x && ta[i] < t)
lower = h;
else
upper = h;
}
return lower + 1;
}
int search2(int r, int y, int x) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int h = (lower + upper) / 2, j = jj[h];
if (rr[j] < r || rr[j] == r && (yy[j] < y || yy[j] == y && xx[j] < x))
lower = h;
else
upper = h;
}
return lower + 1;
}
int query(int i, int k) {
if (state[i] == 1) {
int x = xx[i] + k;
return search1(x, tb[i]) - search1(x, ta[i]);
} else {
int r = rr[i], y = (yy[i] + k) % cc[i];
return search2(r, y, k + 1) - search2(r, y, 0);
}
}
void count_routes(int n_, int m, int p, int ij[][2], int q, int *kk) {
static int hh1[N], hh2[N], pp[N * 2];
int h, i, j;
n = n_;
memset(hh1, -1, n * sizeof *hh1), memset(hh2, -1, n * sizeof *hh2);
for (h = 0; h < m; h++) {
i = ij[h][0], j = ij[h][1];
if (hh1[i] == -1)
hh1[i] = h;
else if (hh2[i] == -1)
hh2[i] = h;
if (hh1[j] == -1)
hh1[j] = h;
else if (hh2[j] == -1)
hh2[j] = h;
}
for (i = 0; i < n; i++) {
h = hh1[i], j = i ^ ij[h][0] ^ ij[h][1];
pp[i << 1 | 0] = j << 1 | (hh1[j] == h ? 1 : 0);
h = hh2[i] == -1 ? hh1[i] : hh2[i], j = i ^ ij[h][0] ^ ij[h][1];
pp[i << 1 | 1] = j << 1 | (hh1[j] == h ? 1 : 0);
}
for (i = 0; i < n * 2; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 0; i < n * 2; i++)
append(pp[i], i);
for (i = 0; i < n * 2; i++)
if (!state[i]) {
for (j = i; !state[j]; j = pp[j])
state[j] = -1;
c = 0;
while (state[j] == -1) {
state[j] = -2, j = pp[j];
c++;
}
r = j, dfs(j, 0, 0);
}
for (i = 0; i < n; i++)
ii[i] = i << 1 | 0;
sort(ii, 0, n, compare_xt);
for (i = 0; i < n; i++)
jj[i] = i << 1 | 0;
sort(jj, 0, n, compare_ryx);
for (h = 0; h < q; h++)
answer(query(p << 1 | 0, kk[h]) + query(p << 1 | 1, kk[h]));
}
