#include "garden.h"
#include "gardenlib.h"
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
static int most_beautiful[150001][2];
static int graph[300001];
// 10^9 < 2^30
static int nxt[30][300001];
// 1 indexing, graph[u] == 0, means no edges connected to it
P++;
// save 2 most_beautiful edges
for (int i = 0; i < M; i++) {
for (int j = 0; j < 2; j++) {
int u = R[i][j] + 1;
int v = R[i][j^1] + 1;
if (most_beautiful[u][0] == 0) {
most_beautiful[u][0] = v;
} else if (most_beautiful[u][1] == 0) {
most_beautiful[u][1] = v;
}
}
}
// build functional graph
for (int u = 1; u <= N; u++) {
for (int j = 0; j < 2; j++) {
int v = most_beautiful[u][j];
if (most_beautiful[v][0] != u || most_beautiful[v][1] == 0)
graph[u + j*N] = v;
else
graph[u + j*N] = v + N;
}
}
// binary lift
for (int u = 1; u <= 2 * N; u++)
nxt[0][u] = graph[u];
for (int p = 1; p < 30; p++)
for (int u = 1; u <= 2 * N; u++)
nxt[p][u] = nxt[p-1][ nxt[p-1][u] ];
for (int i = 0; i < Q; i++) {
int res = 0;
for (int j = 1; j <= N; j++) {
int u = j;
for (int p = 0; p < 30; p++)
if (G[i] >> p & 1)
u = nxt[p][u];
res += u == P || u == P + N;
}
answer(res);
}
}
