#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
using namespace std;
const int maxn = 150001;
int n, m, p, g[maxn][101];
vector <int> v[maxn];
int go(int node, int prev){
if(v[node].size() == 1) return v[node][0];
if(v[node][0] == prev) return v[node][1];
return v[node][0];
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N;
m = M;
p = P;
for(int i = 0 ; i < M ; i++){
v[R[i][0]].push_back(R[i][1]);
v[R[i][1]].push_back(R[i][0]);
}
for(int node = 0 ; node < n ; node++){
g[node][0] = node;
for(int step = 1 ; step <= 100 ; step++){
int cur = g[node][step - 1];
int prev = -1;
if(step - 2 >= 0) prev = g[node][step - 2];
g[node][step] = go(cur, prev);
}
}
vector <int> ans(101);
for(int step = 1 ; step <= 100 ; step++){
for(int node = 0 ; node < n ; node++){
ans[step] += g[node][step] == p;
}
}
for(int i = 0 ; i < Q ; i++){
answer(ans[G[i]]);
}
}
