#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 150000;
const int MAXM = 150000;
const int MAXL = 29;
int Rf[MAXN];
int Rs[MAXN];
int succreal[MAXN][MAXL];
int succfake[MAXN][MAXL];
bool _second_path_real[MAXN][MAXL];
bool _second_path_fake[MAXN][MAXL];
int succ(int x, int k)
{
int ans = x;
bool fake = false;
int cur = pow(2,MAXL);
int curval = MAXL;
while (k!=0) {
while (cur>k) cur/=2,curval--;
k-=cur;
if (!fake) {
if (_second_path_real[ans][curval]) fake = true;
ans = succreal[ans][curval];
} else {
if (!_second_path_fake[ans][curval]) fake = false;
ans = succfake[ans][curval];
}
}
return ans;
}
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++) {
int 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 (int i = 0; i<n; i++) if (Rs[i] == -1) Rs[i] = Rf[i];
for (int 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 (int i = 1; i<=MAXL; i++) {
for (int 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 (int i = 0; i<q; i++) {
int a = 0;
for (int j = 0; j<n; j++) if (succ(j,G[i]) == p) a++;
answer(a);
}
}
