#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
stack<int> st;
vector<bool> visited, mark;
vector<int> sz, scc;
vector<vector<int> > graph, tgraph, dj;
void dfs(int node, int d, int t){
if (visited[node])return;
visited[node]=1;
dj[t][node]=d;
for (auto num:graph[node])dfs(num, d+1, t);
st.push(node);
}
void dfs2(int node, int c){
if (mark[node])return;
mark[node]=1;
scc[node]=c;
++sz[c];
for (auto num:tgraph[node])dfs2(num, c);
}
void count_routes(int n, int m, int start, int r[][2], int q, int g[]){
graph.clear();
tgraph.clear();
sz.clear();
visited.clear();
scc.clear();
dj.clear();
graph.resize(2*n);
tgraph.resize(2*n);
vector<vector<pii> > edges(n);
for (int i=0; i<m; ++i){
edges[r[i][0]].pb(mp(i, r[i][1]));
edges[r[i][1]].pb(mp(i, r[i][0]));
}
for (int i=0; i<n; ++i)sort(edges[i].begin(), edges[i].end());
for (int i=0; i<n; ++i){
tgraph[i].pb(edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0));
graph[edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0)].pb(i);
if (edges[i].size()>=2){
tgraph[i+n].pb(edges[i][1].se+(edges[edges[i][1].se][0].fi==edges[i][1].fi?n:0));
graph[edges[i][1].se+(edges[edges[i][1].se][0].fi==edges[i][1].fi?n:0)].pb(i+n);
}
else{
tgraph[i+n].pb(edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0));
graph[edges[i][0].se+(edges[edges[i][0].se][0].fi==edges[i][0].fi?n:0)].pb(i+n);
}
}
scc.resize(2*n);
sz.resize(2*n, 0);
dj.resize(2, vector<int>(2*n, -1));
visited.resize(2*n, 0);
dfs(start, 0, 0);
mark.clear();
mark.resize(2*n, 0);
for (int i=0; i<2*n; ++i)if (!visited[i])dfs(i, 0, 0);
while (st.size()){
int node=st.top();
st.pop();
if (mark[node])continue;
dfs2(node, node);
}
dj.assign(2, vector<int>(2*n, -1));
visited.assign(2*n, 0);
dfs(start, 0, 0);
visited.assign(2*n, 0);
dfs(start+n, 0, 1);
for (int i=0; i<q; ++i){
int ans=0;
for (int j=0; j<n; ++j){
bool can=0;
for (int p=0; p<2; ++p){
if (dj[p][j]==-1)continue;
if (sz[scc[start+p*n]]==1){
if (dj[p][j]==g[i])can=1;
}
else if (dj[p][j]<=g[i]&&!((g[i]-dj[p][j])%sz[scc[start+p*n]]))can=1;
}
ans+=can;
}
answer(ans);
}
}
