#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
// create graph
vector<vi> adj; adj.resize(N);
int m=0;
vi U, V, ReverseEdge;
RE(i,M) {
U.push_back(R[i][0]); V.push_back(R[i][1]);
adj[U[m]].push_back(m); ReverseEdge.push_back(m+1); m++;
U.push_back(R[i][1]); V.push_back(R[i][0]);
adj[U[m]].push_back(m); ReverseEdge.push_back(m-1); m++;
}
// fill next
vi nxt;
RE(i,m) {
bool found = 0;
FOR(v,adj[V[i]]) {
if(v == ReverseEdge[i]) continue;
nxt.push_back(v);
found = 1;
break;
}
if(!found)
nxt.push_back(ReverseEdge[i]);
}
// fill prev
vector<vi> prev; prev.resize(m);
RE(i,m) prev[nxt[i]].pb(i);
vector<bool> visited;
visited.assign(m,0);
vi funct; funct.assign(m,-1);
vi functRes; functRes.assign(m,-1);
// iniitial queue
queue<int> q;
FOR(x,adj[P]) {
int y = ReverseEdge[x];
q.push(y);
visited[y] = 1;
funct[y] = 1;
functRes[y] = nxt[y];
}
// bfs
while(!q.empty()) {
int u=q.front(); q.pop();
FOR(v,prev[u]) {
if(visited[v]) continue;
q.push(v);
visited[v] = 1;
funct[v] = funct[u] + 1;
functRes[v] = functRes[u];
}
}
RE(i,Q) {
int ans = 0;
RE(j,N) {
int u = adj[j][0];
int ng = G[i];
int times = 0;
while(functRes[u] != -1) {
times++;
if(functRes[functRes[u]] == u) {
int totFunct = funct[u] + funct[functRes[u]];
if((ng%totFunct) == 0) {
ans++;
break;
}
}
if(times > 2) {
break;
}
if(functRes[u] == u) {
if((ng%funct[u]) == 0) ans++;
break;
}
if(ng < funct[u]) break;
ng -= funct[u];
u = functRes[u];
if(ng == 0) {
ans++;
break;
}
}
}
answer(ans);
}
}
