#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=15e4;
// came in: 0 - best, 1 - not best
vector<pair<int,int>> in[NN][2];
int anss[NN+10];
int out[NN+10][2];
vector<int> cnt[2*NN+10];
bool vis[NN+10][2];
int dd[NN+10][2];
bool end_type(int x,int y)
{
return (x!=out[y][1]);
}
pair<int,int> go(pair<int,int> x)
{
int y=out[x.fi][x.se];
return {y,end_type(x.fi,y)};
}
void add_edge(int x,int y)
{
if(out[x][1]==-1)
out[x][1]=y;
else if(out[x][0]==-1)
out[x][0]=y;
return;
}
void reverse_edge(int x,int t,int y)
{
in[y][end_type(x,y)].push_back({x,t});
return;
}
int cycle(int P,int t,int N)
{
for(int i=0;i<N;i++)
vis[i][0]=vis[i][1]=false;
int ans=0;
pair<int,int> x={P,t};
for(;!vis[x.fi][x.se];ans++,x=go(x))
{
vis[x.fi][x.se]=true;
}
if(x==make_pair(P,t))
return ans;
return 10*N;
}
void paths(int P,int t,int N,int l)
{
for(int i=0;i<l;i++)
cnt[i].clear();
for(int i=0;i<N;i++)
vis[i][0]=vis[i][1]=false;
vis[P][t]=true;
dd[P][t]=0;
queue<pair<int,int>> qq;
qq.push({P,t});
while(!qq.empty())
{
auto v=qq.front();
qq.pop();
if(v.se==1)
cnt[dd[v.fi][v.se]%l].push_back(dd[v.fi][v.se]);
for(auto y:in[v.fi][v.se])
{
if(!vis[y.fi][y.se])
{
vis[y.fi][y.se]=true;
dd[y.fi][y.se]=dd[v.fi][v.se]+1;
qq.push(y);
}
}
}
return;
}
int cnt_paths(int id,int mx)
{
if(cnt[id].empty() || cnt[id][0]>mx)
return 0;
int bg=0,en=cnt[id].size()-1;
while(bg<en)
{
int mid=(bg+en+1)/2;
if(cnt[id][mid]<=mx)
bg=mid;
else
en=mid-1;
}
return bg+1;
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[])
{
for(int i=0;i<N;i++)
out[i][0]=out[i][1]=-1;
for(int i=0;i<M;i++)
{
add_edge(R[i][0],R[i][1]);
add_edge(R[i][1],R[i][0]);
}
for(int i=0;i<N;i++)
{
if(out[i][0]==-1)
out[i][0]=out[i][1];
reverse_edge(i,0,out[i][0]);
reverse_edge(i,1,out[i][1]);
}
for(int t:{0,1})
{
int l=cycle(P,t,N);
paths(P,t,N,l);
for(int i=0;i<Q;i++)
{
if(l==10*N && G[i]>l)
continue;
anss[i]+=cnt_paths(G[i]%l,G[i]);
}
}
for(int i=0;i<Q;i++)
answer(anss[i]);
return;
}
