#include "garden.h"
#include "gardenlib.h"
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
///Directed Graph
///Determine the number of nodes that can follow a path and finish in P
///Duplicate all the nodes
struct edge
{
int to;
int w;
};
bool byW(edge e1,edge e2)
{
return e1.w<e2.w;
}
vector<edge> graph[250001]; //Given graph
vector<int> adjList[500005]; //Directed graph with duplicated nodes
vector<int> revGraph[500005]; //Reversed graph of the directed graph
void buildGraph(int N) ///Builds a directed graph with the given graph
{
///Real node uses its principal edge
///Duplicated node uses its secondary edge
for(int u=0;u<N;u++){
edge e=graph[u][0]; //Principal edge
int v=e.to;
if(graph[v][0].to!=u || graph[v].size()==1){ //Not principal edge of v or v has only one edge
adjList[u].push_back(v); //Connect with real node
}
else{
adjList[u].push_back(v+N); //Connect with duplicated node
}
e=graph[u][1]; //Secondary edge
v=e.to;
if(graph[v][0].to!=u || graph[v].size()==1){ //Not principal edge of v or v has only one edge
adjList[u+N].push_back(v); //Connect with real node
}
else{
adjList[u+N].push_back(v+N); //Connect with duplicated node
}
}
}
void Reverse(int N)
{
for(int u=0;u<2*N;u++){
if(adjList[u].size()==0) continue;
int v=adjList[u][0];
revGraph[v].push_back(u);
}
}
queue<int> q;
int d[500005][2]; //Distance from P and P+N
int color[500005];
int cycle_size=0;
int inCycle[3]; //P and P+N
void BFS(int s,int op,int P,int N)
{
d[s][op]=0;
color[s]=op;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();
for(int v: revGraph[u]){
if(color[v]!=op){
q.push(v);
d[v][op]=d[u][op]+1;
}
else{ //There is a cycle
cycle_size=d[u][op]+1;
if(s==P) inCycle[0]=1;
if(s==P+N) inCycle[1]=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];
edge e={v,i};
graph[u].push_back(e);
e.to=u;
graph[v].push_back(e);
}
for(int u=0;u<N;u++){
sort(graph[u].begin(),graph[u].end(),byW); //We get the principal edge in [0] and secondary edge in [1]
}
buildGraph(N);
Reverse(N);
for(int u=0;u<2*N;u++){
color[u]=-1;
d[u][0]=d[u][1]=-1;
}
BFS(P,0,P,N); //Computes the distance from all nodes to node P
BFS(P+N,1,P,N); //Computed the distance from all nodes to node P+N (duplicated node)
for(int i=0; i<Q; i++){
int k=G[i];
int total=0;
for(int u=0;u<N;u++){
if(d[u][0]==-1) continue;
int D=k-d[u][0];
if(D<0) continue;
if(D==0){
total++;
continue;
}
if(inCycle[0]){
if(cycle_size>0 && D%cycle_size==0) total++;
}
}
for(int u=0;u<N;u++){
if(d[u][1]==-1) continue;
int D=k-d[u][1];
if(D<0) continue;
if(D==0){
total++;
continue;
}
if(inCycle[1]){
if(cycle_size>0 && D%cycle_size==0) total++;
}
}
answer(total);
}
}
