#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 bfs(v<v<int>> &adj, int node, int dist, v<int> &dists) {
queue<pii> q;
q.push({node, dist});
while (q.size()) {
pii front = q.front();
int cur=front.fi;
int dist=front.se;
q.pop();
if (dists[cur]!=-1) continue;
dists[cur] = dist;
for (int nex: adj[cur]) {
q.push({nex, dist+1});
}
}
}
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;
}
// SUBTASK 2
if (SUBTASK==2) {
// 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;
//}
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;
}
// SUBTASK 3
// Find cycle lengths
int p_cycle0 = 1e9+100;
int p_cycle1 = 1e9+100;
int cur=2*P;
for (int i=0; i<2*N; i++) {
cur=next[cur];
if (cur==2*P) {
p_cycle0 = i+1;
break;
}
}
cur=2*P+1;
for (int i=0; i<2*N; i++) {
cur=next[cur];
if (cur==2*P+1) {
p_cycle1 = i+1;
break;
}
}
// Construct reverse graph
v<v<int>> adj (2*N, v<int>(0));
for (int i=0; i<2*N; i++) {
adj[next[i]].push_back(i);
}
v<int> dists0 (2*N, -1);
v<int> dists1 (2*N, -1);
// Populate dists0/1
bfs(adj, 2*P, 0, dists0);
bfs(adj, 2*P+1, 0, dists1);
for (int i=0; i<Q; i++) {
int K=G[i];
int count=0;
for (int j=0; j<N; j++) {
if ((K-dists0[2*j])%p_cycle0==0 || (K-dists1[2*j])%p_cycle1==0)
count++;
}
answer(count);
}
}
