#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define v vector
#define pii pair<int,int>
#define ll long long
#define pli pair<long long, int>
#define fi first
#define se second
using namespace std;
int LIMIT = 29;
int jump_amount(v<v<int>> jumps, int a, int amount) {
for (int j=LIMIT; j>=0; j--) {
if (1<<j <= amount) {
amount -= 1<<j;
a = jumps[j][a];
}
}
return a;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
v<int> first (N, -1);
v<int> second (N, -1);
v<int> next (2*N, -1);
// Build first and second choices
for (int i=0; i<M; i++) {
int a=R[i][0];
int b=R[i][1];
if (first[a]==-1) first[a]=b;
else if (second[a]==-1) second[a]=b;
if (first[b]==-1) first[b]=a;
else if (second[b]==-1) second[b]=a;
}
for (int i=0; i<N; i++) {
if (second[i]==-1) second[i]=first[i];
}
// Build next
for (int i=0; i<N; i++) {
if (first[first[i]]==i) next[2*i]=first[i]*2+1;
else next[2*i]=first[i]*2;
if (first[second[i]]==i) next[2*i+1]=second[i]*2+1;
else next[2*i+1]=second[i]*2;
}
//for (int i=0; i<N; i++) {
//cerr<<i<<": ("<<next[2*i]/2<<","<<next[2*i]%2<<") ("<<next[2*i+1]/2<<","<<next[2*i+1]%2<<")"<<endl;
//}
int SUBTASK = 2;
if (SUBTASK==1) {
assert(Q==1);
int K=G[0];
int count = 0;
for (int i=0; i<N; i++) {
int cur=2*i;
for (int j=0; j<K; j++) {
cur = next[cur];
}
if (cur/2 == P) count++;
}
answer(count);
return;
}
// Both subtasks 2&3
// Build jump pointers
v<v<int>> jumps (LIMIT+1, v<int> (2*N, 0));
jumps[0] = next;
for (int i=1; i<=LIMIT; i++) {
for (int j=0; j<2*N; j++) {
jumps[i][j] = jumps[i-1][jumps[i-1][j]];
}
}
//for (int j=0; j<2*N; j++) {
//cerr<<j<<" ";
//}cerr<<endl;
//for (int i=0; i<=3; i++) {
//for (int j=0; j<2*N; j++) {
//cerr<<jumps[i][j]<<" ";
//}cerr<<endl;
//}
if (SUBTASK==2) {
for (int i=0; i<Q; i++) {
int K=G[i];
int count=0;
for (int j=0; j<N; j++) {
int end = jump_amount(jumps, 2*j, K);
//cerr<<j<<" jumps "<<K<<" to ("<< end/2<<","<<end%2<<")"<<endl;
if (end/2 == P) count++;
}
answer(count);
}
return;
}
}
