#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N_ = 150005;
int ans, n, m, target;
vector<int> edges[N_];
int d;
bool used[N_];
void dfs(int u,int p=-1){
used[u] = true;
if(d<0)return;
//~ cout << u << ' ';
if(d == 0){
if(u == target){
ans++;
}d--;
return;
}d--;
if(d<0)return;
if(edges[u].size() > 1){
if(edges[u][0] != p){
dfs(edges[u][0],u);
}else {
dfs(edges[u][1],u);
}
}else if(p == -1 && edges[u].size())dfs(edges[u][0],u);
if(d<0)return;
if(p!=-1)dfs(p,u);
return;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
target = P;
n = N, m = M;
for(int i=0;i<m;i++){
edges[R[i][0]].pb(R[i][1]);
edges[R[i][1]].pb(R[i][0]);
}
for(int i=0;i<Q;i++){
ans=0;
for(int j=0;j<n;j++){
d = G[i];
//~ cout << "dfsing " << j << ": ";
if(j != 0 && !used[j])assert(false);
dfs(j);
//~ cout<<'\n';
}answer(ans);
}return;
}
