#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
const int MXN=3e5+10;
int n,m,st,nxt[2][MXN],d[2][MXN],cycle[2];
bool vis[2][MXN];
vector <int> adj[MXN];
vector <pii> adj2[MXN];
void dfs(int u,int state,int d_u){
d[state][u]=d_u;
vis[state][u]=true;
for(int v:adj[u]){
if(v==state*n+st) cycle[state]=d_u+1;
if(!vis[state][v]) dfs(v,state,d_u+1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n=N,m=M,st=P;
memset(d,-1,sizeof(d));
cycle[0]=cycle[1]=-1;
for(int i=0;i<m;i++){
adj2[R[i][0]].push_back({i,R[i][1]});
adj2[R[i][1]].push_back({i,R[i][0]});
}
for(int i=0;i<n;i++){
sort(adj2[i].begin(),adj2[i].end());
nxt[0][i]=adj2[i][0].s;
nxt[1][i]=adj2[i][adj2[i].size()>1].s;
}
for(int i=0;i<n;i++){
bool ok=(i==nxt[0][nxt[0][i]]);
adj[n*ok+nxt[0][i]].push_back(i);
ok=(i==nxt[0][nxt[1][i]]);
adj[n*ok+nxt[1][i]].push_back(i+n);
}
dfs(st,0,0);
dfs(st+n,1,0);
for(int i=0;i<Q;i++){
int cnt=0;
for(int u=0;u<n;u++){
for(int state=0;state<2;state++){
bool ok=true;
if(d[state][u]==-1) ok=false;
else if(cycle[state]==-1) ok=(d[state][u]==G[i]);
else{
int rem=G[i]-d[state][u];
ok=(rem%cycle[state]==0 && rem>=0);
}
if(ok){
cnt++;
break;
}
}
}
answer(cnt);
}
}
