#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]);
}
auto node = [&](int u, int v) {
if (adj[v][0] == u)
return N+v;
else
return v;
};
const int J = 29;
vector<vector<int>> succ(J+1, vector<int>(2*N, -1));
for (int i = 0; i < N; ++i) {
succ[0][node(-1, i)] = node(i, adj[i][0]);
for (int v : adj[i]) {
if (v != adj[i][0] or adj[i].size() == 1)
succ[0][node(v, i)] = node(i, adj[i][0]);
else
succ[0][node(v, i)] = node(i, adj[i][1]);
}
}
for (int j = 1; j <= J; ++j) {
for (int u = 0; u < 2*N; ++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 = node(-1, i);
for (int j = J; j >= 0; --j) {
if (K & (1 << j)) u = succ[j][u];
}
if (u == P or u == N+P) ++cnt;
}
answer(cnt);
}
}
