#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,cur1,cur2;
void succ()
{
fake = false;
while (cur2) {
curval = (int) floor(log2(cur2));
cur = pow(2,curval);
cur2-=cur;
if (!fake) {
if (_second_path_real[cur1][curval]) fake = true;
cur1 = succreal[cur1][curval];
} else {
if (!_second_path_fake[cur1][curval]) fake = false;
cur1 = succfake[cur1][curval];
}
}
}
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, cur2 = G[i];
for (cur1 = 0; cur1<n; cur1++) { succ(); if (cur1 == p) a++; }
answer(a);
}
}
