#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
int const n=15e4+3;
vpi adj[n];
vi pre[2*n];
int d[2*n][2];
bitset<2>vis[2*n];
int cycle[2];
int P;
int N;
void dfs(int now, int w, bool r)
{
if(vis[now][r])
{
if(now==P||now==P+N)
{
cycle[r]=w;
}
return;
}
d[now][r]=w;
vis[now][r]=1;
trav(chi,pre[now])
{
dfs(chi,w+1,r);
}
}
void count_routes(int N1, int M, int p, int R[][2], int Q, int G[]){
N=N1;
P=p;
F0R(i,M)
{
int u = R[i][0];
int v = R[i][1];
adj[u].pb({M-i,v});
adj[v].pb({M-i,u});
}
F0R(i,N)
{
sort(all(adj[i]));
reverse(all(adj[i]));
}
F0R(i,N)
{
int nxt = adj[i][0].se;
if(adj[nxt][0].se == i)
{
nxt+=N;
}
pre[nxt].pb(i);
if(sz(adj[i])>1)nxt = adj[i][1].se;
else nxt = adj[i][0].se;
if(adj[nxt][0].se == i)
{
nxt+=N;
}
pre[nxt].pb(i+N);
}
F0R(i,2*N)
{
d[i][0]=d[i][1]=-1;
}
dfs(P,0,0);
dfs(P+N,0,1);
F0R(r,2)
{
cycle[r]=-1;
}
F0R(j,Q)
{
int ans=0;
F0R(i,N)
{
F0R(r,2)
{
if(d[i][r]!=-1
&&G[j]>=d[i][r])
{
if(G[j]-d[i][r]==0)
{
++ans;
}
else if(cycle[r]!=-1
&&(G[j]-d[i][r])%cycle[r]==0)
{
++ans;
}
}
}
}
answer(ans);
}
}
