#include<bits/stdc++.h>
using namespace std;
const int N=400100;
typedef long long ll;
vector<int> listeCourante[N];
int pass[N],areteCourante[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++)
areteCourante[R[i][0]]++,areteCourante[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(areteCourante[R[i][0]]==1){
listeCourante[v0+1].push_back(u0);
listeCourante[v0+1].push_back(u0+1);
}else
listeCourante[v0+1].push_back(u0+pass[R[i][0]]);
}else
{
if(areteCourante[R[i][0]]==1){
listeCourante[v0].push_back(u0);
listeCourante[v0].push_back(u0+1);
}else
listeCourante[v0].push_back(u0+pass[R[i][0]]);
}
}
if(pass[R[i][1]]<=1)
{
if(!pass[R[i][0]]){
if(areteCourante[R[i][1]]==1){
listeCourante[u0+1].push_back(v0);
listeCourante[u0+1].push_back(v0+1);
}else
listeCourante[u0+1].push_back(v0+pass[R[i][1]]);
}else
{
if(areteCourante[R[i][1]]==1){
listeCourante[u0].push_back(v0);
listeCourante[u0].push_back(v0+1);
}else
listeCourante[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:listeCourante[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:listeCourante[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]--;
}
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]){
rs++;
}
else if(d0[2*i]!=-1 && c0!=-1 && G[j]>=d0[2*i] &&(G[j]-d0[2*i])%c0==0){
rs++;
}
else if(d1[2*i]!=-1 && c1!=-1 && G[j]>=d1[2*i] && (G[j]-d1[2*i])%c1==0){
rs++;
}
}
answer(rs);
}
}
