#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#include <cassert>
#include "garden.h"
#include "gardenlib.h"
#define SZ(x) (LL)(x.size())
#define FR(i,a,b) for(LL i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
typedef std::pair<LD,LD> PLD;
using namespace std;
//cycle detection?
//store radj
const int MAXN=150015;
int to[2*MAXN];
vector<int> radj[2*MAXN];
int dist[2*MAXN][2];
bool vis[2*MAXN];
int len[2][2], type[2];
bool check(int t, int d) {
if (d<0 || type[t]==-1) return false;
if (d==0) return true;
if (type[t]==t) return (d%len[t][t]==0);
if (type[(t+1)%2]==t) {
d%=len[t][(t+1)%2]+len[(t+1)%2][t];
return check((t+1)%2, d-len[t][(t+1)%2]);
}
return check((t+1)%2, d-len[t][(t+1)%2]);
}
void bfs(int s, int t, int n) {
queue<int> q;
FOR(i,2*n+1) vis[i]=false;
dist[s][t]=0;
q.push(s);
while (!q.empty()) {
int u=q.front();
q.pop();
if (vis[u]) continue;
vis[u]=1;
for (int v:radj[u]) {
if (dist[v][t]==-1) {
dist[v][t]=dist[u][t]+1;
q.push(v);
}
}
}
}
void cyc(int s, int t, int n) {
FOR(i,2*n+1) vis[i]=false;
int start;
if (t==0) start=s;
else start=s+n;
int u=to[start], d=1;
while (!vis[u]) {
vis[u]=true;
if (u==s) {
type[t]=0;
len[t][0]=d;
return;
}
if (u==s+n) {
type[t]=1;
len[t][1]=d;
return;
}
u=to[u];
d++;
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
int adj[n][2];
memset(adj,-1,sizeof(adj));
FOR(i,m){
int u=r[i][0], v=r[i][1];
if (adj[u][0]==-1) adj[u][0]=v;
else if (adj[u][1]==-1) adj[u][1]=v;
if (adj[v][0]==-1) adj[v][0]=u;
else if (adj[v][1]==-1) adj[v][1]=u;
}
FOR(i,2*n) radj[i].clear();
FOR(i,n){
int v=adj[i][0];
if (adj[v][0]==i) v+=n;
to[i]=v;
radj[v].push_back(i);
if (adj[i][1]!=-1){
int v=adj[i][1];
if (adj[v][0]==i) to[i+n]=v+n;
else to[i+n]=v;
}
else to[i+n]=v;
radj[to[i+n]].push_back(i+n);
}
memset(dist,-1,sizeof(dist));
memset(len,-1,sizeof(len));
type[0]=type[1]=-1;
bfs(p,0,n);
bfs(p+n,1,n);
cyc(p,0,n);
cyc(p,1,n);
FOR(i,q){
int k=g[i], ans=0;
for (int u=0; u<n; u++) {
bool can=false;
if (dist[u][0]!=-1) {
int rem=k-dist[u][0];
can|=check(0,rem);
}
if (dist[u][1]!=-1) {
int rem=k-dist[u][1];
can|=check(1,rem);
}
if (can) ans++;
}
answer(ans);
}
}
