#include "garden.h"
#include "gardenlib.h"
using namespace std;
#include <vector>
#define INF 999999999
struct node{
int p=-1;//0
bool g1=false;//1
bool g2=false;//1
bool l1=false;//1
bool l2=false;//1
bool f=false;//valid start?
vector<int> v;//0
int z1=INF;
int z2=INF;
node(){}
};
int e,n;
vector<node> v;
void count_routes(int N, int m, int E, int w[][2], int Q, int G[]){
n=N;e=E;
//0 input trails
v.resize(n*2,node());
int a,b;
for (int i=0;i<m;i++){
a=w[i][0];
b=w[i][1];
if (v[b].p==-1){b+=n;}
if (v[a].p==-1){
v[a].p=b;
v[b].v.push_back(a);
a+=n;
}else if (v[a+n].p==-1){
v[a+n].p=b;
v[b].v.push_back(a+n);
}
b%=n;
if (v[b].p==-1){
v[b].p=a;
v[a].v.push_back(b);
}else if (v[b+n].p==-1){
v[b+n].p=a;
v[a].v.push_back(b+n);
}
}
for (int i=0;i<n;i++){
if (v[i+n].p==-1){
v[i+n].p=v[i].p;
}
}
//1 find loops
int ra,rb;
a=e;
ra=0;
while (!v[a].g1){
v[a].g1=true;
ra++;
a=v[a].p;
}
if (a!=e){ra=1;}
a=e+n;
rb=0;
while (!v[a].g2){
v[a].g2=true;
rb++;
a=v[a].p;
}
if (a!=e+n){rb=1;}
a=e;//print(e);
for (int i=0;i<ra;i++){
// print(a);
v[a].l1=true;
a=v[a].p;
}
a=e+n;
for (int i=0;i<rb;i++){
v[a].l2=true;
a=v[a].p;
}
//2 grow trees
vector<pair<int,int>> q;
pair<int,int> p;
a=e;
for (int i=0;i<ra;i++){
q.clear();
q.push_back({a,(ra-i)%ra});
while (!q.empty()){
p=q[q.size()-1];//print(p.first);
q.pop_back();
if (v[p.first].l1&&p.second!=((ra-i)%ra)){continue;}
v[p.first].z1=p.second;
for (int j:v[p.first].v){
q.push_back({j,p.second+1});
}
}
a=v[a].p;
}
a=e+n;
for (int i=0;i<rb;i++){
q.clear();
q.push_back({a,(rb-i)%rb});
while (!q.empty()){
p=q[q.size()-1];
q.pop_back();
if (v[p.first].l2&&p.second!=((rb-i)%rb)){continue;}
v[p.first].z2=p.second;
for (int j:v[p.first].v){
q.push_back({j,p.second+1});
}
}
a=v[a].p;
}
// for (int i=0;i<n*2;i++){print(v[i].z1);print(v[i].z2);}
//3 answer queries
int z;
for (int i=0;i<Q;i++){
a=G[i];
z=0;
for (int j=0;j<n;j++){
if (v[j].z1==a){
z++;
}else if (ra!=1 && a>=v[j].z1 && ((a-v[j].z1)%ra==0)){
z++;
}else if (v[j].z2==a){
z++;
}else if (rb!=1 && a>=v[j].z2 && ((a-v[j].z2)%rb==0)){
z++;
}
}
answer(z);
}
}
