#include"garden.h"
#include"gardenlib.h"
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int n; // num nodes
int m; // num edges
vector<vector<int>>nodes; // lowest node and second lowest node
vector<int>nxt;
vector<int>vis;
vector<int>dist;
int cycle_size;
void add_conn(int node,int dest){
if(nodes[node][0]==-1){
nodes[node]={dest,dest};
}else if(nodes[node][0]==nodes[node][1]){
nodes[node][1]=dest;
}
}
void dfs(int node){
if(vis[nxt[node]]!=-1){
if(vis[nxt[node]]==0)
cycle_size=vis[node]+1;
else
cycle_size=-1;
return;
}
vis[nxt[node]]=vis[node]+1;
dfs(nxt[node]);
}
int get_dist(int node){
if(dist[node]!=-1)
return dist[node];
dist[node]=1e9;
dist[node]=get_dist(nxt[node])+1;
return dist[node];
}
vector<int>get(int Q,int G[],int P){
vis=vector<int>(2*n,-1);
vis[P]=0;
dfs(P);
dist=vector<int>(2*n,-1);
dist[P]=0;
vector<int>res(Q);
if(cycle_size==-1){
unordered_map<int,int>mp;
for(int i=0;i<n;i++)
mp[get_dist(2*i)]++;
for(int i=0;i<Q;i++)
res[i]+=mp[G[i]];
}else{
for(int i=0;i<Q;i++){
for(int j=0;j<n;j++){
int dist=get_dist(2*j);
if(dist<=G[i]&&dist%cycle_size==G[i]%cycle_size){
res[i]++;
}
}
}
}
return res;
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
n=N;
m=M;
nodes=vector<vector<int>>(n,{-1,-1});
nxt.resize(2*n);
for(int i=0;i<m;i++){
add_conn(R[i][0],R[i][1]);
add_conn(R[i][1],R[i][0]);
}
for(int i=0;i<2*n;i++){
nxt[i]=2*nodes[i/2][i%2];
if(nodes[nxt[i]/2][0]==i/2&&nodes[nxt[i]/2][1]!=-1)
nxt[i]++;
}
vector<int>res1=get(Q,G,2*P);
vector<int>res2=get(Q,G,2*P+1);
for(int i=0;i<Q;i++){
answer(res1[i]+res2[i]);
}
}
