#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)v.size())
#define all(v) (v).begin(),(v).end()
#define ll long long
void count_routes(int n, int m, int k, int R[][2], int Q, int G[]){
vector<int> vai(2*n,-1);
vector<vector<int>> adjr(2*n);
L(i,0,m-1){
auto [a,b]=R[i];
bool oka=(vai[a]==-1);
bool okb=(vai[b]==-1);
if(vai[a]==-1){
if(okb)vai[a]=b+n;
else vai[a]=b;
}
else if(vai[a+n]==-1){
if(okb)vai[a+n]=b+n;
else vai[a+n]=b;
}
if(vai[b]==-1){
if(oka)vai[b]=a+n;
else vai[b]=a;
}
else if(vai[b+n]==-1){
if(oka)vai[b+n]=a+n;
else vai[b+n]=a;
}
}
L(i,0,n-1){
if(vai[i+n]==-1)vai[i+n]=vai[i];
}
L(i,0,2*n-1){
adjr[vai[i]].push_back(i);
}
vector<int> vis(2*n);
vector<int> st;
st.push_back(0);
int at=0;
vis[at]=1;
while(!vis[vai[at]]){
vis[vai[at]]=1;
st.push_back(vai[at]);
at=vai[at];
}
vector<int> ciclo(1,at);
vector<int> pos(2*n,-1);
while(st.back()!=at){
ciclo.push_back(st.back());
st.pop_back();
}
reverse(all(ciclo));
vector<int> prof(2*n,-1);
vector<int> rep(2*n);
L(i,0,sz(ciclo)-1){
pos[ciclo[i]]=i;
rep[ciclo[i]]=i;
prof[ciclo[i]]=0;
}
auto busca=[&](auto&& self, int at)->int{
if(prof[at]!=-1)return prof[at];
return prof[at]=self(self,vai[at])+1;
};
L(i,0,2*n-1){
if(prof[i]==-1)busca(busca,i);
}
for(int receba=0;receba<Q;receba++){
int d=G[receba];
int resp=0;
if(prof[k]==0){
L(i,0,n-1){
if(d<prof[i])continue;
d-=prof[i];
int at=rep[i];
d-=(pos[k]-at+sz(ciclo))%sz(ciclo);
if(d>=0 && (d%sz(ciclo))==0)resp++;
}
}
else{
vector<pair<int,int>> fila;
fila.push_back({0,k});
while(!fila.empty()){
auto [prf,v]=fila.back();
fila.pop_back();
if(prf==d){
if(v<n)resp++;
}
else{
for(auto a:adjr[v])fila.push_back({prf+1,a});
}
}
}
if(prof[k+n]==0){
L(i,0,n-1){
if(d<prof[i])continue;
d-=prof[i];
int at=rep[i];
d-=(pos[k+n]-at+sz(ciclo))%sz(ciclo);
if(d>=0 && (d%sz(ciclo))==0)resp++;
}
}
else{
vector<pair<int,int>> fila;
fila.push_back({0,k+n});
while(!fila.empty()){
auto [prf,v]=fila.back();
fila.pop_back();
if(prf==d){
if(v<n)resp++;
}
else{
for(auto a:adjr[v])fila.push_back({prf+1,a});
}
}
}
answer(resp);
}
}
