#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
pair<int,int> adj[150010][2];
// vector<pair<int,int>> rev[150010][2];
pair<int,int> jump[150010][31][2];
int dg[150010];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
memset(adj,-1,sizeof(adj));
for(int i = 0;i<M;i++){
int u = R[i][0];
int v = R[i][1];
// cout << u << ' ';
// cout << v << '\n';
dg[u]++;
dg[v]++;
if(dg[u]==1){
// adj[u][0] = adj[u][1] = {v,dg[v]==1};
jump[u][0][0] = jump[u][0][1] = {v,dg[v]==1};
}
else if(dg[u]==2){
// adj[u][1] = {v,dg[v]==1};
jump[u][0][1] = {v,dg[v]==1};
}
if(dg[v]==1){
jump[v][0][0] = jump[v][0][1] = {u,dg[u]==1};
// adj[v][0] = adj[u][1] = {u,dg[u]==1};
}
else if(dg[v]==2){
jump[v][0][1] = {u,dg[u]==1};
// adj[v][1] = {u,dg[u]==1};
}
}
// for(int i = 0;i<N;i++){
// cout << jump[i][0][0].first<<' '<< jump[i][0][0].second<<' ' << jump[i][0][1].first<<' '<< jump[i][0][1].second<<'\n';
// }
// for(int i = 0;i<N;i++){
// rev[adj[i][0].first][adj[i][0].second].push_back({i,0});
// rev[adj[i][1].first][adj[i][1].second].push_back({i,1});
// }
for(int i = 1;i<30;i++){
for(int j=0;j<N;j++){
jump[j][i][0]=jump[jump[j][i-1][0].first][i-1][jump[j][i-1][0].second];
jump[j][i][1]=jump[jump[j][i-1][1].first][i-1][jump[j][i-1][1].second];
}
}
// cout << jump[0][0][0].first << ' ' << jump[0][0][0].second<<'\n';
for(int i = 0;i<Q;i++){
int ans = 0;
for(int j = 0;j<N;j++){
pair<int,int> a = {j,0};
for(int k = 0;k<30;k++){
if((1<<k)&G[i]){
a = jump[a.first][k][a.second];
}
}
if(a.first == P){
ans++;
}
}
answer(ans);
}
}
