#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include<vector>
using namespace std;
///Duplicate nodes
///Directed graph
///Determine the number of nodes that can follow a path and end in P in exactly K steps
vector<int> adjList[300005];
vector<int> original[150005];
short vis[300005];
void buildGraph(int N) ///Creates duplicated and reversed graph
{
///Real node uses its prncipal edge
///Duplicated node uses its secondary edge
for(int u=0;u<N;u++){
int v=original[u][0]; //Principal edge
if(original[v][0]!=u || original[v].size()==1){
adjList[v].push_back(u);
}
else{
adjList[v+N].push_back(u);
}
if(original[u].size()==1) continue;
v=original[u][1]; //Secondary edge
if(original[v][0]!=u || original[v].size()==1){
adjList[v].push_back(u+N);
}
else{
adjList[v+N].push_back(u+N);
}
}
}
int color[300005];
int d[300005][2];
int C[2]={-1,-1}; //Cycle Size
int inCycle[2];
int t=0;
void dfs(int u) ///Computes distance from P and P+N (duplicated node) to all nodes
{
color[u]=1;
for(int v: adjList[u]){
if(color[v]==0){
d[v][t]=d[u][t]+1;
dfs(v);
}
else if(color[v]==1){ //P/P+N is on a cycle
C[t]=d[u][t]+1;
inCycle[t]=1;
}
}
color[u]=-1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0;i<M;i++){
int u=R[i][0];
int v=R[i][1];
original[u].push_back(v);
original[v].push_back(u);
}
buildGraph(N);
for(int i=0;i<2*N;i++){
d[i][0]=d[i][1]=1000000000;
}
d[P][0]=0;
dfs(P);
t++;
for(int i=0;i<2*N;i++){
color[i]=0;
}
d[P+N][1]=0;
dfs(P+N);
for(int i=0;i<Q;i++){ //For each query
int k=G[i];
int total=0;
for(int u=0;u<N;u++){ //For each node
for(int j=0;j<2;j++){ //Checks if the distance is 0 modulo C
if(d[u][j]==1000000000) continue; //Not reachable
if(inCycle[j]){ //Cycle
int D=k-d[u][j];
if(D>=0){
if(D%C[j]==0) total++;
}
}
else{
int D=k-d[u][j]; //Distance is exactly the same
if(D==0) total++;
}
}
}
answer(total);
}
}
