#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int MAX_N = 2*1e5;
pii bl[2*MAX_N][30];
int max_p[MAX_N];
int to_id(pii pos){
return pos.first*MAX_N+ pos.second;
}
vector<vector<pii>> adj;
int get_step(int id, int d){
int cur = id;
for(int i = 0; i<30; i++){
if((d& (1<<i)) != 0){
if(bl[cur][i].first == max_p[bl[cur][i].second]){
cur = bl[cur][i].second + MAX_N;
}
else{
cur = bl[cur][i].second;
}
}
}
return cur;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
adj.resize(N);
for(int i = 0; i <M; i++){
adj[R[i][0]].push_back(pii(i, R[i][1]));
adj[R[i][1]].push_back(pii(i, R[i][0]));
}
for(int i = 0; i<N; i++){
bl[i][0] = adj[i][0];
max_p[i] = adj[i][0].first;
if(adj[i].size()>1){
bl[i+MAX_N][0] = adj[i][1];
}
else{
bl[i+MAX_N][0] = adj[i][0];
}
}
for(int i = 1; i<30; i++){
for(int j = 0; j<N; j++){
if(bl[j][i-1].first == max_p[bl[j][i-1].second]){
bl[j][i] = bl[bl[j][i-1].second + MAX_N][i-1];
}
else{
bl[j][i] = bl[bl[j][i-1].second][i-1];
}
}
for(int j = 0; j<N+MAX_N; j++){
if(bl[j][i-1].first == max_p[bl[j][i-1].second]){
bl[j][i] = bl[bl[j][i-1].second + MAX_N][i-1];
}
else{
bl[j][i] = bl[bl[j][i-1].second][i-1];
}
}
}
for(int i = 0; i<Q; i++){
int res= 0;
for(int j = 0; j<N; j++){
if(get_step(j, G[i])%MAX_N == P){
res++;
}
}
answer(res);
}
}
