#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 150000;
const int MAXM = 150000;
int Rf[MAXN];
int Rs[MAXN];
int succreal[MAXN][30];
int succfake[MAXN][30];
bool _second_path_real[MAXN][30];
bool _second_path_fake[MAXN][30];
bool fake; int cur,curval,a,x,y,i,j;
int succ(int x, int k)
{
fake = false;
while (k) {
curval = (int) floor(log2(k));
cur = pow(2,curval);
k-=cur;
if (!fake) {
if (_second_path_real[x][curval]) fake = true;
x = succreal[x][curval];
} else {
if (!_second_path_fake[x][curval]) fake = false;
x = succfake[x][curval];
}
}
return x;
}
void count_routes(int n, int m, int p, int R[][2], int q, int G[])
{
fill(Rf,Rf+n,-1);
fill(Rs,Rs+n,-1);
for (int i = 0; i<m; i++) {
x = R[i][0], y = R[i][1];
if (Rf[x] == -1) Rf[x] = y;
else if (Rs[x] == -1) Rs[x] = y;
if (Rf[y] == -1) Rf[y] = x;
else if (Rs[y] == -1) Rs[y] = x;
}
for (i = 0; i<n; i++) if (Rs[i] == -1) Rs[i] = Rf[i];
for (j = 0; j<n; j++) {
succreal[j][0] = Rf[j];
if (Rf[Rf[j]] == j) _second_path_real[j][0] = true;
succfake[j][0] = Rs[j];
if (Rf[Rs[j]] == j) _second_path_fake[j][0] = true;
}
for (i = 1; i<30; i++) {
for (j = 0; j<n; j++) {
if (_second_path_real[j][i-1]) {
succreal[j][i] = succfake[succreal[j][i-1]][i-1];
_second_path_real[j][i] = _second_path_fake[succreal[j][i-1]][i-1];
} else {
succreal[j][i] = succreal[succreal[j][i-1]][i-1];
_second_path_real[j][i] = _second_path_real[succreal[j][i-1]][i-1];
}
if (_second_path_fake[j][i-1]) {
succfake[j][i] = succfake[succfake[j][i-1]][i-1];
_second_path_fake[j][i] = _second_path_fake[succfake[j][i-1]][i-1];
} else {
succfake[j][i] = succreal[succfake[j][i-1]][i-1];
_second_path_fake[j][i] = _second_path_real[succfake[j][i-1]][i-1];
}
}
}
for (i = 0; i<q; i++) {
a = 0;
for (j = 0; j<n; j++) if (succ(j,G[i]) == p) a++;
answer(a);
}
}
