#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
vector<vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
set<pair<int,int>> nodes;
for (int i = 0; i < N; ++i) {
nodes.insert({-1, i});
for (int v : adj[i]) nodes.insert({i, v});
}
int siz = nodes.size();
vector<bool> inP(siz, false);
map<pair<int,int>,int> idx;
int idx_ = 0;
for (auto node : nodes) {
idx[node] = idx_;
if (node.second == P) inP[idx_] = true;
++idx_;
}
nodes.clear();
const int J = 29;
vector<vector<int>> succ(J+1, vector<int>(siz, -1));
for (int i = 0; i < N; ++i) {
succ[0][idx[{-1, i}]] = idx[{i, adj[i][0]}];
for (int v : adj[i]) {
if (v != adj[i][0] or adj[i].size() == 1)
succ[0][idx[{v, i}]] = idx[{i, adj[i][0]}];
else
succ[0][idx[{v, i}]] = idx[{i, adj[i][1]}];
}
}
for (int j = 1; j <= J; ++j) {
for (int u = 0; u < siz; ++u) {
succ[j][u] = succ[j-1][ succ[j-1][u] ];
}
}
for(int it = 0; it < Q; ++it) {
int K = G[it];
int cnt = 0;
for (int i = 0; i < N; ++i) {
int u = idx[{-1, i}];
for (int j = J; j >= 0; --j) {
if (K & (1 << j)) u = succ[j][u];
}
if (inP[u]) ++cnt;
}
answer(cnt);
}
}
