#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
int k, t, res = 0;
vector<vector<pair<int, int>>> g;
void dfs(int u, int p, int d = 0) {
if (d == k) {
res += (u == t);
return;
}
int i = p;
vector<pair<int, int>> a;
for (auto [v, w] : g[u]) {
a.push_back({w, v});
}
sort(a.begin(), a.end());
if (a.size() == 1) {
dfs(a[0].second, u, d + 1);
}
else {
if (a[0].second == p) {
dfs(a[1].second, u, d + 1);
}
else {
dfs(a[0].second, u, d + 1);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
t = P;
g.resize(N);
for (int i = 0; i < M; i++) {
int u = R[i][0], v = R[i][1];
g[u].push_back({v, i});
g[v].push_back({u, i});
}
for (int q = 0; q < Q; q++) {
res = 0;
k = G[q];
for (int i = 0; i < N; i++) {
dfs(i, -1);
}
answer(res);
}
}
