#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[150005];
int nxt[300005][30];
int low[150005];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
memset(low,0x3f,sizeof(low));
for (int i=0; i<M; i++) {
for (int j=0; j<2; j++) {
low[R[i][j]] = min(low[R[i][j]],i);
}
graph[R[i][0]].push_back(pi(R[i][1],i));
graph[R[i][1]].push_back(pi(R[i][0],i));
}
for (int i=0; i<N; i++) {
if(low[graph[i][0].first] == graph[i][0].second){
nxt[2*i][0] = graph[i][0].first * 2 + 1;
}
else{
nxt[2*i][0] = graph[i][0].first * 2;
}
if(graph[i].size() == 1){
nxt[2*i+1][0] = nxt[2*i][0];
}
else{
if(low[graph[i][1].first] == graph[i][1].second){
nxt[2*i+1][0] = graph[i][1].first * 2 + 1;
}
else{
nxt[2*i+1][0] = graph[i][1].first * 2;
}
}
}
for (int i=1; i<30; i++) {
for (int j=0; j<2*N; j++) {
nxt[j][i] = nxt[nxt[j][i-1]][i-1];
}
}
for (int i=0; i<Q; i++) {
int time = G[i];
int cnt = 0;
for (int j=0; j<N; j++) {
int pos = 2*j;
for (int k=0; k<30; k++) {
if((time >> k) & 1){
pos = nxt[pos][k];
}
}
if(pos == 2*P || pos == 2*P+1){
cnt++;
}
}
answer(cnt);
}
}
