#include <bits/stdc++.h>
#include "gardenlib.h"
#include "garden.h"
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ff first
#define ss second
const int MAXN = 15e4+10;
const int MAXM = 15e4+10 ;
const int MAXQ = 2005 ;
const int inf=1e9+10 ;
using namespace std;
int p ;
pii best[MAXN], secBest[MAXN] , dp[MAXN][2] ;
void inc(int i, int j)
{
if(dp[i][j].ss != -1)
dp[i][j].ff ++ ;
}
pii calcDp(int i, int j)
{
if(i==p) return pii(0,j) ;
if(dp[i][j].ff == -2 ) return dp[i][j]= pii(inf,-1) ;
if(dp[i][j].ff!=-1) return dp[i][j] ;
dp[i][j].ff = -2;
if(j==0)
dp[i][j] = calcDp(best[i].ff, best[i].ss) ;
else dp[i][j] = calcDp(secBest[i].ff, secBest[i].ss) ;
inc(i,j) ;
return dp[i][j] ;
}
void count_routes(int n , int m , int P, int r[][2] , int q, int g[])
{
p=P ;
lp(i,0,MAXN)
best[i] = secBest[i] = pii(-1,0) ;
lp(i,0,MAXN)
lp(j,0,2) dp[i][j] = pii(-1,-1) ;
lp(i,0,m)
lp(j,0,2)
{
int a = r[i][j] , b = r[i][!j] ;
if(best[a].ff == -1){
best[a].ff = b ;
if( best[b].ff == -1 || best[b].ff == a )
best[a].ss = 1 ;
}
else if(secBest[a].ff == -1)
{
secBest[a].ff = b ;
if( best[b].ff == -1 || best[b].ff == a )
secBest[a].ss = 1 ;
}
}
lp(i,0,n)
if(secBest[i].ff == -1)
secBest[i] = best[i] ;
lp(i,0,n)
lp(j,0,2)
if(dp[i][j].ff == -1 && best[i].ff != -1 )
dp[i][j] = calcDp(i,j) ;
dp[p][0] = calcDp(best[p].ff, best[p].ss) ;
inc(p,0) ;
dp[p][1] = calcDp(secBest[p].ff, secBest[p].ss) ;
inc(p,1) ;
int dist[3] = {dp[p][0].ff , dp[p][1].ff , dp[p][0].ff+dp[p][1].ff} ;
int edge[2] = {dp[p][0].ss , dp[p][1].ss} ;
lp(i,0,q)
{
int ans = 0 ;
lp(j,0,n)
{
int k = dp[j][0].ss , temp=dp[j][0].ff;
if(k == -1) continue ;
int forNow = g[i] - temp ;
if(forNow == 0) ans ++ ;
if(forNow<=0 || edge[k]==-1) continue ;
if(edge[k] == k && forNow%dist[k] == 0) ans++ ;
else
{
if(edge[!k] == !k && forNow-dist[k] >= 0)
{if((forNow-dist[k])%dist[!k] == 0) ans ++ ;}
else if(edge[!k] == k )
{
if( forNow%(dist[2]) == 0 ) ans ++ ;
else if(forNow>=dist[k] && (forNow-dist[k])%(dist[2])==0) ans++ ;
}
}
}
answer(ans) ;
}
}
