#include<bits/stdc++.h>
using namespace std;
const int N=400100;
typedef long long ll;
vector<int> lista[N];
int pass[N],grau[N],d0[N],d1[N];
void answer(int X);
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0;i<M;i++)
grau[R[i][0]]++,grau[R[i][1]]++;
for(int i=0;i<M;i++)
{
int u0=2*R[i][0],v0=2*R[i][1];
if(pass[R[i][0]]<=1)
{
if(!pass[R[i][1]]){
if(grau[R[i][0]]==1){
lista[v0+1].push_back(u0);
lista[v0+1].push_back(u0+1);
}else
lista[v0+1].push_back(u0+pass[R[i][0]]);
}else
{
if(grau[R[i][0]]==1){
lista[v0].push_back(u0);
lista[v0].push_back(u0+1);
}else
lista[v0].push_back(u0+pass[R[i][0]]);
}
}
if(pass[R[i][1]]<=1)
{
if(!pass[R[i][0]]){
if(grau[R[i][1]]==1){
lista[u0+1].push_back(v0);
lista[u0+1].push_back(v0+1);
}else
lista[u0+1].push_back(v0+pass[R[i][1]]);
}else
{
if(grau[R[i][1]]==1){
lista[u0].push_back(v0);
lista[u0].push_back(v0+1);
}else
lista[u0].push_back(v0+pass[R[i][1]]);
}
}
pass[R[i][0]]++;
pass[R[i][1]]++;
}
queue<int> f;
f.push(2*P);
d0[2*P]=1;
int c0=-1;
while(!f.empty())
{
int u=f.front();
f.pop();
for(int v:lista[u])
{
if(!d0[v])
{
d0[v]= d0[u]+1;
f.push(v);
}else
{
c0=d0[u];
}
}
}
f.push(2*P+1);
d1[2*P+1]=1;
int c1=-1;
while(!f.empty())
{
int u=f.front();
f.pop();
for(int v:lista[u])
{
if(!d1[v])
{
d1[v]= d1[u]+1;
f.push(v);
}else
{
c1=d1[u];
}
}
}
for(int i=0;i<=2*N;i++){
d0[i]--,d1[i]--;
// if(i%2==0)
// cout<<d1[i]<<"<\n";
}
// cout<<c0<<" "<<c1<<'\n';
for(int j=0;j<Q;j++)
{
int rs=0;
for(int i=0;i<N;i++)
{
if(G[j]==d0[2*i] || G[j]==d1[2*i]){
// cout<<i<<" "<<d0[2*i]<<" "<<d1[2*i]<<"\n";
rs++;
}
else if(d0[2*i]!=-1 && c0!=-1 && G[j]>=d0[2*i] &&(G[j]-d0[2*i])%c0==0){
// cout<<i<<"<\n";
rs++;
}
else if(d1[2*i]!=-1 && c1!=-1 && G[j]>=d1[2*i] && (G[j]-d1[2*i])%c1==0){
// cout<<i<<"<<\n";
rs++;
}
}
answer(rs);
}
}
// void answer(int X)
// {
// cout<<X<<"\n";
// }
// int n, M,P, R[100][2], Q, G[100];
// int main()
// {
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// cin>>n>>M>>P>>Q;
// for(int i=0;i<M;i++)
// cin>>R[i][0]>>R[i][1];
// for(int i=0;i<Q;i++)
// cin>>G[i];
// count_routes(n,M,P,R,Q,G);
// return 0;
// }
