#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> next (2*N, -1);
for (int i=0; i<M; i++) {
int a=R[i][0];
int b=R[i][1];
if (next[2*a]==-1 && next[2*b]==-1) {
next[2*a]=2*b+1;
next[2*b]=2*a+1;
continue;
}
if (next[2*a]==-1) next[2*a]=2*b;
else if (next[2*a+1]==-1) next[2*a+1]=2*b;
if (next[2*b]==-1) next[2*b]=2*a;
else if (next[2*b+1]==-1) next[2*b+1]=2*a;
}
for (int i=0; i<N; i++) {
if (next[2*i+1]==-1) next[i*2+1]=next[i*2];
}
int SUBTASK = 1;
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
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<N; j++) {
jumps[i][j] = jumps[i-1][jumps[i-1][j]];
}
}
if (SUBTASK==2) {
for (int i=0; i<Q; i++) {
int K=G[i];
int count=0;
for (int j=0; j<N; j++) {
if (jump_amount(jumps, 2*j, K)/2 == P) count++;
}
answer(count);
}
return;
}
}
