#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 150000, MAXL = 30;
int anc[2*MAXN][MAXL], par[2*MAXN], parF[MAXN], parS[MAXN], P1, P2;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
memset(par, -1, sizeof(par));
memset(anc, -1, sizeof(anc));
P1 = P;
P2 = P + N;
vector<int> adj[N];
for(int i = 0; i < M; i++){
adj[R[i][0]].pb(R[i][1]);
adj[R[i][1]].pb(R[i][0]);
}
for(int i = 0; i < N; i++){
if(adj[i].size() == 1) adj[i].pb(adj[i][0]);
parF[i] = adj[i][0];
parS[i] = adj[i][1];
}
for(int i = 0; i < N; i++){
if(i == parF[parF[i]]){
par[i] = parF[i] + N;
par[parF[i]] = i + N;
}
else{
par[i] = parF[i];
}
if(i == parF[parS[i]]){
par[i + N] = parS[i] + N;
}
else{
par[i + N] = parS[i];
}
}
for(int i = 0; i < 2*N; i++){
anc[i][0] = par[i];
}
for(int i = 1; i < MAXL; i++){
for(int x = 0; x < 2*N; x++){
anc[x][i] = anc[anc[x][i - 1]][i - 1];
}
}
for(int k = 0; k < Q; k++){
int K = G[k], ans = 0;
for(int j = 0; j < N; j++){
int ret = j;
for(int i = 0; i < MAXL; i++){
if(K&(1 << i)){
ret = anc[ret][i];
}
}
if(ret == P1 or ret == P2){
ans++;
}
}
answer(ans);
}
}
