#include "garden.h"
#include "gardenlib.h"
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
int adj[150000][3];
int par[300000][30];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
for (int i = 0; i < M; i++) {
int a = R[i][0], b = R[i][1];
if (adj[a][2] < 2) adj[a][adj[a][2]++] = b;
if (adj[b][2] < 2) adj[b][adj[b][2]++] = a;
}
for (int i = 0; i < N; i++) {
if (adj[i][2] == 0) continue;
if (adj[i][2] == 1) adj[i][1] = adj[i][0];
if (adj[adj[i][0]][0] == i) par[i][0] = 150000 + adj[i][0];
else par[i][0] = adj[i][0];
if (adj[adj[i][1]][0] == i) par[150000 + i][0] = 150000 + adj[i][1];
else par[150000 + i][0] = adj[i][1];
}
for (int j = 1; j < 30; j++) {
for (int i = 0; i < N; i++) {
par[i][j] = par[par[i][j - 1]][j - 1];
par[150000 + i][j] = par[par[150000 + i][j - 1]][j - 1];
}
}
for (int it = 0; it < Q; it++) {
int res = 0;
for (int i = 0; i < N; i++) {
if (adj[i][2] == 0) continue;
int c = i;
for (int j = 0, k = G[it]; j < 30; j++, k >>= 1) {
if (k & 1) c = par[c][j];
}
if (c % 150000 == P) res++;
}
answer(res);
}
}
