#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define maxN 150005
#define INF LLONG_MAX
#define INT 1000000001
using namespace std;
vector <int> adj[maxN];
long long N,P,s,i,dis[2][maxN],k[2][maxN],c[2];
bool mar[maxN];
long long dfs(int n,int d){
long long y;
if(d>2*N) return INT;
if(adj[n].size()>0 && (adj[n][0]!=s || adj[n].size()==1)) {if(dis[0][n]!=INF) return dis[0][n];}
else {if(dis[1][n]!=INF) return dis[1][n];}
if(adj[n].size()>0 && (adj[n][0]!=s || adj[n].size()==1)) y=adj[n][0];
else y=adj[n][1];
if(adj[n][0]!=s || adj[n].size()==1) {
s=n;
dis[0][n]=dfs(y,d+1)+1;
if(n==adj[y][0]) k[0][n]=k[1][y];
else k[0][n]=k[0][y];
if(adj[n].size()==1){
k[1][n]=k[0][n];
dis[1][n]=dis[0][n];
}
return dis[0][n];}
else {
s=n;
dis[1][n]=dfs(y,d+1)+1;
if(n==adj[y][0]) k[1][n]=k[1][y];
else k[1][n]=k[0][y];
return dis[1][n];}
}
long long period(int x,int d){
if(d>3*N) return INF;
int y;
if(adj[x].size()>0 && (adj[x][0]!=s || adj[x].size()==1)) y=adj[x][0];
else y=adj[x][1];
if(y==P) {
if(x==adj[P][0]) {if(c[0]==-5) c[0]=1; else c[1]=1;}
else {if(c[0]==-5) c[0]=0; else c[1]=0;}
return d+1;
}
s=x;
return period(y,d+1);
}
void count_routes(int n,int m,int p,int r[][2],int q,int g[]){
N=n;
P=p;
for(i=0;i<m;i++){
adj[r[i][0]].push_back(r[i][1]);
adj[r[i][1]].push_back(r[i][0]);
}
for(i=0;i<n;i++){
dis[0][i]=dis[1][i]=INF;
}
dis[0][p]=0;
dis[1][p]=0;
k[0][p]=0;
k[1][p]=1;
for(i=0;i<n;i++){
s=-5;
dis[0][i]=dfs(i,0);
s=adj[i][0];
dis[1][i]=dfs(i,0);
}
long long t1,t2;
s=-5;
c[0]=-5;
t1=period(p,0);
if(adj[p].size()>0) {
s=adj[p][0];
t2=period(p,0);
}
else t2=INF;
for(i=0;i<q;i++){
long long ans=0;
for(int j=0;j<n;j++){
if(k[0][j]==0 && dis[0][j]<=g[i]){
if(dis[0][j]==g[i]) {ans++; continue;}
if(dis[0][j]+t1==g[i]) {ans++; continue;}
if(c[0]==0){
if((g[i]-dis[0][j])%t1==0) {ans++; continue;}}
else{
if((g[i]-dis[0][j]-t1)%t2==0) {ans++; continue;}
}
}
if(k[0][j]==1 && dis[0][j]<=g[i]){
if(dis[0][j]==g[i]) {ans++; continue;}
if(dis[0][j]+t2==g[i]) {ans++; continue;}
if(c[1]==1){
if((g[i]-dis[0][j])%t2==0) {ans++; continue;}}
else{
if((g[i]-dis[0][j]-t2)%t1==0) {ans++; continue;}
}
}
}
answer(ans);
}
}
