#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];
// 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;
}
}
}
for (int u = 1; u <= N; u++) {
for (int j = 0; j < 2; j++) {
int v = most_beautiful[u][j];
if (v == 0) continue;
if (most_beautiful[v][0] != u || most_beautiful[v][1] == 0)
graph[u + j*N] = v;
else
graph[u + j*N] = v + N;
}
}
for (int i = 0; i < Q; i++) {
int res = 0;
for (int j = 1; j <= N; j++) {
int cur = j;
for (int k = 0; k < G[i]; k++) {
cur = graph[cur];
}
res += cur == P || cur == P + N;
}
answer(res);
}
}
