#include <iostream>
#include<bits/stdc++.h>
using namespace std;
void answer(int X);
std::vector<int> BestPath;
vector<int> SecondBestPath;
int getLoopSize(int base,int prev,int node,vector<bool>& Visited,int steps){
int wnode=node;
if(BestPath[node]==prev && SecondBestPath[node]!=-1){
wnode=wnode+150001;
}
if(wnode==base){
return steps;
}
int b=base;
if(Visited[wnode]==true){
return -1;
}
Visited[wnode]=true;
if(BestPath[node]==prev && SecondBestPath[node]!=-1){
return getLoopSize(base,node,SecondBestPath[node],Visited,steps+1);
}
return getLoopSize(base,node,BestPath[node],Visited,steps+1);
}
int dfsTo(int prev,int node,vector<int>& Distance,int target){
int wnode=node;
if(BestPath[node]==prev && SecondBestPath[node]!=-1){
wnode=wnode+150001;
}
if(wnode==target){
return 0;
}
if(Distance[wnode]!=0){
return Distance[wnode];
}
Distance[wnode]=-1;
int d;
if(BestPath[node]==prev && SecondBestPath[node]!=-1){
d=dfsTo(node,SecondBestPath[node],Distance,target);
}
else{
d =dfsTo(node,BestPath[node],Distance,target);
}
if(d==-1){
return -1;
}
Distance[wnode]=d+1;
return d+1;
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
BestPath = vector<int>(N,-1);
SecondBestPath = vector<int>(N,-1);
for(int i=0;i<M;i++){
if(BestPath[R[i][0]]==-1){
BestPath[R[i][0]]=R[i][1];
}
else if(SecondBestPath[R[i][0]]==-1){
SecondBestPath[R[i][0]]=R[i][1];
}
if(BestPath[R[i][1]]==-1){
BestPath[R[i][1]]=R[i][0];
}
else if(SecondBestPath[R[i][1]]==-1){
SecondBestPath[R[i][1]]=R[i][0];
}
}
vector<bool> Visited(2*150010,false);
int loopSize=getLoopSize(P,P,BestPath[P],Visited,1);
int loopSizep=-2;
vector<bool> Visitedp(2*150010,false);
if(SecondBestPath[P]!=-1){
loopSizep=getLoopSize(P+150001,P,SecondBestPath[P],Visitedp,1);
}
vector<int> Ans(Q);
vector<int> Distance (2*150010);
vector<int> DistanceD (350000);
int maxi=0;
for(int i=0;i<N;i++){
int dis=dfsTo(-1,i,Distance,P);
if(dis!=-1){
maxi=max(maxi,dis);
DistanceD[dis]=DistanceD[dis]+1;
}
}
maxi+=1+loopSize;
if(loopSize!=-1){
for(int i=loopSize;i<maxi+1;i++){
DistanceD[i]=DistanceD[i-loopSize]+DistanceD[i];
}
}
for(int i=0;i<Q;i++){
if(G[i]<maxi+1){
Ans[i]=DistanceD[G[i]];
}
else if(loopSize!=-1){
Ans[i]=DistanceD[G[i]-((G[i]-maxi-1)/loopSize+1)*loopSize];
}
}
if(loopSizep!=-2){
Distance=vector<int> (2*150010);
DistanceD=vector<int>(350000);
int maxi=0;
for(int i=0;i<N;i++){
int dis=dfsTo(-1,i,Distance,P+150001);
if(dis!=-1){
maxi=max(maxi,dis);
DistanceD[dis]=DistanceD[dis]+1;
}
}
maxi+=1+loopSizep;
if(loopSizep!=-1){
for(int i=loopSizep;i<maxi+1;i++){
DistanceD[i]=DistanceD[i-loopSizep]+DistanceD[i];
}
}
for(int i=0;i<Q;i++){
if(G[i]<maxi+1){
Ans[i]=DistanceD[G[i]]+Ans[i];
}
else if(loopSizep!=-1){
Ans[i]=DistanceD[G[i]-((G[i]-maxi-1)/loopSizep+1)*loopSizep]+Ans[i];
}
}
}
for(int i=0;i<Q;i++){
answer(Ans[i]);
}
return;
}
