#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
using namespace std;
const int maxn = 150001;
const int maxk = 31;
int n, m, p;
pair <int, int> g[maxn][maxk][2];
vector <int> v[maxn];
int go1(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];
}
int go2(int node, int idx){
if(v[node].size() == 1) return v[node][0];
if(idx == 1) return v[node][0];
return v[node][1];
}
int calc(int node, int steps){
int prev = -1;
while(steps--){
int pcur = node;
node = go1(node, prev);
prev = pcur;
}
return node;
}
int lift(int node, int s){
pair <int, int> cur = make_pair(node, 1);
for(int i = maxk - 1 ; i >= 0 ; i--){
if((s >> i) & 1){
cur = g[cur.first][i][cur.second];
}
}
return cur.first;
}
int idx(int node, int h){
if(v[node][0] == h) return 0;
return 1;
}
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++){
for(int k = 0 ; k < 2 ; k++){
int nxt = go2(node, k);
g[node][0][k] = make_pair(nxt, idx(nxt, node));
}
}
for(int j = 1 ; j < maxk ; j++){
for(int node = 0 ; node < n ; node++){
for(int k = 0 ; k < 2 ; k++){
auto c = g[node][j - 1][k];
auto nxt = g[c.first][j - 1][c.second];
g[node][j][k] = nxt;
}
}
}
for(int i = 0 ; i < Q ; i++){
int ans = 0;
for(int node = 0 ; node < n ; node++){
ans += lift(node, G[i]) == p;
}
answer(ans);
}
}
