#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});
}
map<pair<int,int>,int> idx;
map<int,pair<int,int>> inv;
int idx_ = 0;
for (auto node : nodes) {
idx[node] = idx_;
inv[idx_] = node;
++idx_;
}
int siz = nodes.size();
const int J = 30;
vector<vector<int>> succ(siz, vector<int>(J+1, -1));
for (int i = 0; i < N; ++i) {
succ[idx[{-1, i}]][0] = idx[{i, adj[i][0]}];
for (int v : adj[i]) {
if (v != adj[i][0])
succ[idx[{v, i}]][0] = idx[{i, adj[i][0]}];
else
succ[idx[{v, i}]][0] = idx[{i, adj[i][1]}];
}
}
for (int j = 1; j <= J; ++j) {
for (int u = 0; u < siz; ++u) {
succ[u][j] = succ[ succ[u][j-1] ][j-1];
}
}
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}];
int k = K;
for (int j = J; j >= 0; --j) {
if (k & (1 << j)) {
k -= 1 << j;
u = succ[u][j];
}
}
auto node = inv[u];
if (node.second == P) ++cnt;
}
answer(cnt);
}
}
