#include "garden.h"
#include "gardenlib.h"
#include "gardenlib.h"
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
int con[150005]={0};
bool have[5][150005];
int st,aaa,bbb;
int con1[5][150005];
int con2[5][150005];
int cir1[5][150005];
int cir2[5][150005];
int in[5][150005];
bool ok=0;
map < pair < int , int > , int > all;
vector < pair < int , int > > Next[1500005];
void F(int x,int y,int deg,int a,int b)
{
//printf("aa %d %d %d %d %d %d\n",x,y,a,b,con1[x][y],con2[x][y]);
int t,aa,bb;
if(have[x][y])
{
if(all.find(make_pair(x,y))!=all.end())
{
ok=1;
t=all[make_pair(x,y)];
aaa=x;
bbb=y;
//printf("%d\n",t);
if(a!=-1&&a>=t)
{
cir1[x][y]=deg-t;
con1[x][y]=cir1[x][y]-(deg-all[make_pair(0,st)]);
con1[x][y]%=cir1[x][y];
}
if(b!=-1&&b>=t)
{
cir2[x][y]=deg-t;
con2[x][y]=cir2[x][y]-(deg-all[make_pair(1,st)]);
con2[x][y]%=cir2[x][y];
}
}
//printf("%d %d %d %d %d %d\n",x,y,con1[x][y],cir1[x][y],con2[x][y],cir2[x][y]);
return;
}
have[x][y]=1;
all[make_pair(x,y)]=deg;
if(x==0&&y==st)
{
a=deg;
if(!ok)
{
cir1[x][y]=-1;
con1[x][y]=0;
}
}
if(x==1&&y==st)
{
b=deg;
if(!ok)
{
cir2[x][y]=-1;
con2[x][y]=0;
}
}
if(y==Next[Next[y][x].second][0].second&&con[Next[y][x].second]>1)
{
aa=1;
bb=Next[y][x].second;
}
else
{
aa=0;
bb=Next[y][x].second;
}
F(aa,bb,deg+1,a,b);
//printf("xx %d %d %d %d %d %d %d\n",x,y,aa,bb,con1[aa][bb],con2[aa][bb],con1[x][y]);
if(con1[aa][bb]!=-1)
{
con1[x][y]=con1[aa][bb]+1;
cir1[x][y]=cir1[aa][bb];
if(ok&&cir1[x][y]!=-1) con1[x][y]%=cir1[x][y];
}
if(con2[aa][bb]!=-1)
{
con2[x][y]=con2[aa][bb]+1;
cir2[x][y]=cir2[aa][bb];
if(ok&&cir2[x][y]!=-1) con2[x][y]%=cir2[x][y];
}
if(x==aaa&&y==bbb) ok=0;
//printf("yy %d %d %d %d %d %d\n",x,y,con1[x][y],cir1[x][y],con2[x][y],cir2[x][y]);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int i=0,j,k,where,ans=0,real;
st=P;
pair < int , int > now;
for(i=0;i<M;i++)
{
Next[R[i][0]].push_back(make_pair(i,R[i][1]));
Next[R[i][1]].push_back(make_pair(i,R[i][0]));
con[R[i][0]]++;
con[R[i][1]]++;
}
for(i=0;i<N;i++) sort(Next[i].begin(),Next[i].end());
for(i=0;i<N;i++)
{
if(i==Next[Next[i][0].second][0].second&&con[Next[i][0].second]>1) in[1][Next[i][0].second]++;
else in[0][Next[i][0].second]++;
if(con[i]>1&&con[Next[i][1].second]>1&&i==Next[Next[i][1].second][0].second) in[1][Next[i][1].second]++;
else if(con[i]>1) in[0][Next[i][1].second]++;
con1[0][i]=-1;
con1[1][i]=-1;
con2[1][i]=-1;
con2[0][i]=-1;
cir1[0][i]=-1;
cir1[1][i]=-1;
cir2[1][i]=-1;
cir2[0][i]=-1;
}
for(i=0;i<N;i++)
{
all.clear();
if(in[0][i]==0) F(0,i,0,-1,-1);
all.clear();
if(in[1][i]==0&&con[i]>1) F(1,i,0,-1,-1);
}
for(i=0;i<N;i++)
{
all.clear();
if(have[0][i]==0) F(0,i,0,-1,-1);
all.clear();
if(have[1][i]==0&&con[i]>1) F(1,i,0,-1,-1);
}
for(i=0;i<Q;i++)
{
ans=0;
for(j=0;j<N;j++)
{
if(G[i]==con1[0][j]||G[i]==con2[0][j]) ans++;
else if(cir1[0][j]!=-1&&con1[0][j]!=-1&&G[i]>=con1[0][j]&&(G[i]-con1[0][j])%cir1[0][j]==0) ans++;
else if(cir2[0][j]!=-1&&con2[0][j]!=-1&&G[i]>=con2[0][j]&&(G[i]-con2[0][j])%cir2[0][j]==0) ans++;
}
answer((int) ans);
}
}
