#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define INF 0x7fffffff
using namespace std;
vector<int>cg[300005],cn[300005];
int n,m,p,ed[300005][2],cur,flag,vis[300005],cnt;
bool state;
struct destination {
int dist[300005],cyc_len=0;
bool in_cyc=false;
}d[2];
void find_cyc(int idx) {
if(vis[idx]==1) {
if(!d[state].in_cyc && idx!=cn[p][state]) return;
d[state].in_cyc=true;
d[state].cyc_len++;
}
if(vis[idx]==2) return;
vis[idx]++;
find_cyc(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0]);
vis[idx]=0;
}
int find_dist(int idx) {
if(cn[p][state]==idx) return d[state].dist[idx]=0;
if(vis[idx]) return d[state].dist[idx];
vis[idx]++;
return d[state].dist[idx]=find_dist(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0])+1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int i,j,k; n=N; m=M; p=P;
for(i=0;i<m;i++) {
ed[i][0]=R[i][0];
ed[i][1]=R[i][1];
ed[i+m][0]=R[i][1];
ed[i+m][1]=R[i][0];
cg[ed[i][0]].push_back(ed[i][1]);
cn[ed[i][0]].push_back(i);
cg[ed[i][1]].push_back(ed[i][0]);
cn[ed[i][1]].push_back(i+m);
d[0].dist[i]=-INF;
d[1].dist[i]=-INF;
d[0].dist[i+M]=-INF;
d[1].dist[i+M]=-INF;
}
state=0;
find_cyc(cn[p][0]);
state=1;
find_cyc(cn[p][1]);
state=0;
for(i=0;i<2*m;i++) {
if(vis[i])continue;
find_dist(i);
}
state=1;
memset(vis,0,sizeof(vis));
for(i=0;i<2*m;i++) {
if(vis[i])continue;
find_dist(i);
}
for(i=0;i<Q;i++) {
cnt=0;
for(j=0;j<n;j++) {
flag=0;
for(k=0;k<2;k++) {
if(d[k].dist[cn[j][0]]<0) continue;
if(d[k].dist[cn[j][0]]==G[i]) {
flag=1;
break;
}
if(d[k].dist[cn[j][0]]<G[i] && d[k].in_cyc && (G[i]-d[k].dist[cn[j][0]])%d[k].cyc_len==0) {
flag=1;
break;
}
}
if(flag)cnt++;
}
answer(cnt);
}
}
