#include "garden.h"
#include "gardenlib.h"
#include "gardenlib.h"
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
long long con[150005]={0};
vector < pair < long long , long long > > Next[150005];
vector < pair < long long , long long > > tt[5][150005];
vector < pair < long long , long long > > tt2[5][150005];
pair < long long , long long > Father[5][150005];
long long how[5][150005];
long long circle[5][150005];
long long Deg[5][150005];
pair < long long , long long > st[5][150005];
bool is[5][150005];
long long in[5][150005]={0};
bool have[5][150005]={0};
long long where[5][150005];
long long ok=0;
long long stx,sty;
vector < pair < long long , long long > > all;
void F(long long x,long long y)
{
if(have[x][y])
{
stx=x;
sty=y;
return;
}
have[x][y]=1;
all.push_back(make_pair(x,y));
if(y==Next[Next[y][x].second][0].second&&con[Next[y][x].second]>1) F(1,Next[y][x].second);
else F(0,Next[y][x].second);
}
void FF(long long x,long long y)
{
long long ok=0,deg=0;
st[x][y]=make_pair(stx,sty);
for(auto i:all)
{
if(i==make_pair(stx,sty))
{
tt[x][y].push_back(i);
Deg[x][y]=deg;
ok=1;
deg=0;
}
if(ok)
{
Father[i.first][i.second]=make_pair(stx,sty);
tt2[stx][sty].push_back(i);
is[i.first][i.second]=1;
how[i.first][i.second]=deg++;
}
else
{
tt[x][y].push_back(i);
Father[i.first][i.second]=make_pair(x,y);
how[i.first][i.second]=deg++;
}
}
if(ok) Deg[stx][sty]=deg;
else Deg[x][y]=deg;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
long long i=0,j,k,where,ans=0,real;
pair < long long , long long > 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]++;
}
for(i=0;i<N;i++)
{
stx=-1;
sty=-1;
all.clear();
if(in[0][i]==0)
{
F(0,i);
FF(0,i);
}
stx=-1;
sty=-1;
all.clear();
if(in[1][i]==0&&con[i]>1)
{
F(1,i);
FF(1,i);
}
}
for(i=0;i<N;i++)
{
stx=-1;
sty=-1;
all.clear();
if(have[0][i]==0)
{
F(0,i);
FF(0,i);
}
stx=-1;
sty=-1;
all.clear();
if(have[1][i]==0&&con[i]>1)
{
F(1,i);
FF(1,i);
}
}
for(i=0;i<Q;i++)
{
ans=0;
for(j=0;j<N;j++)
{
now=make_pair(0,j);
real=G[i];
where=j;
while(!is[now.first][now.second])
{
real+=how[now.first][now.second];
now=Father[now.first][now.second];
if(real<Deg[now.first][now.second])
{
where=tt[now.first][now.second][real].second;
real=0;
break;
}
else
{
real-=Deg[now.first][now.second];
now=st[now.first][now.second];
}
}
if(real)
{
real+=how[now.first][now.second];
now=Father[now.first][now.second];
where=tt2[now.first][now.second][(real)%Deg[now.first][now.second]].second;
}
if(where==P) ans++;
}
answer((int) ans);
}
}
/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2
*/
