#include "garden.h"
#include "gardenlib.h"
#include <stdlib.h>
#define N 150000
#define M 150000
#define Q 2000
#define L 29 /* L = floor(log2(10^9)) */
#define INF 0x3f3f3f3f
void append(int **eh, int *eo, int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
int *eh[N], eo[N], *fj[M * 2], fo[M * 2];
int qu1[M * 2], cnt1, qu2[M * 2], cnt2; char src[M * 2], dest[M * 2], visited[M * 2];
int kk[Q], ans[Q], q;
void dfs(int i, int r) {
int o, h;
visited[i] = 1;
qu2[cnt2++] = i;
if (src[i])
for (h = 0; h < q; h++) {
int p = kk[h] < cnt2 ? qu2[cnt2 - 1 - kk[h]] : qu1[(r + kk[h] - (cnt2 - 1)) % cnt1];
if (dest[p])
ans[h]++;
}
for (o = fo[i]; o--; ) {
int j = fj[i][o];
if (visited[j] != 1)
dfs(j, r);
}
cnt2--;
}
void count_routes(int n, int m, int p, int ii[][2], int q_, int *kk_) {
static int pp[M * 2];
int h, i, j, o;
q = q_;
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (h = 0; h < m; h++)
append(eh, eo, ii[h][0], h << 1 | 0), append(eh, eo, ii[h][1], h << 1 | 1);
for (i = 0; i < n; i++) {
int h1, h2;
h1 = INF, h2 = INF;
for (o = eo[i]; o--; ) {
h = eh[i][o];
if (h1 > h)
h2 = h1, h1 = h;
else if (h2 > h)
h2 = h;
}
src[h1] = 1;
if (h2 == INF)
pp[h1 ^ 1] = h1;
else {
pp[h1 ^ 1] = h2;
for (o = eo[i]; o--; ) {
h = eh[i][o];
if (h != h1)
pp[h ^ 1] = h1;
}
}
}
for (o = eo[p]; o--; ) {
h = eh[p][o];
dest[h ^ 1] = 1;
}
for (h = 0; h < q; h++)
kk[h] = kk_[h] - 1;
for (i = 0; i < m * 2; i++)
fj[i] = (int *) malloc(2 * sizeof *fj[i]);
for (i = 0; i < m * 2; i++)
append(fj, fo, pp[i], i);
for (i = 0; i < m * 2; i++)
if (!visited[i]) {
j = i;
while (!visited[j])
visited[j] = -1, j = pp[j];
cnt1 = 0;
while (visited[j] == -1) {
visited[j] = 1, j = pp[j];
qu1[cnt1++] = j;
}
cnt2 = 0;
for (h = 0; h < cnt1; h++)
dfs(qu1[h], h);
}
for (h = 0; h < q; h++)
answer(ans[h]);
}
