#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
const int MAXN = 155555;
using namespace std;
vector<int> g[MAXN];
int dfs(int v, int p, int k){
if (k == 0) return v;
if (g[v].size() == 1 || g[v][0] != p) return dfs(g[v][0], v, k - 1);
return dfs(g[v][1], v, k - 1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
for (int i = 0; i < M; i++){
g[R[i][0]].push_back(i);
g[R[i][1]].push_back(i);
}
for (int i = 0; i < N; i++){
if (g[i].size() < 2) continue;
int j = min_element(g[i].begin(), g[i].end()) - g[i].begin();
swap(g[i][0], g[i][j]);
j = min_element(g[i].begin() + 1, g[i].end()) - g[i].begin();
swap(g[i][1], g[i][j]);
g[i].resize(2);
}
for (int i = 0; i < N; i++){
int x = g[i][0];
g[i][0] = (R[x][0] == i ? R[x][1] : R[x][0]);
if (g[i].size() == 2){
x = g[i][1];
g[i][1] = (R[x][0] == i ? R[x][1] : R[x][0]);
}
}
for (int it = 0; it < Q; it++){
int ans = 0;
for (int i = 0; i < N; i++){
if (dfs(i, i, G[it]) == P) ans++;
}
answer(ans);
}
}
