#include"garden.h"
#include"gardenlib.h"
#include<vector>
#include<algorithm>
#define INF 1000000000
using namespace std;
int Exit[300005]; //daca i<=N sunt in nodul i si ies prin cea mai mare muchie, i>N ies prin a doua cea mai mare
int Prim[150005],Sec[150005];
bool Viz[300005];
int Dist[300005];
int Sol[2005];
void getDist(int nod)
{
Viz[nod]=1;
if(!Viz[Exit[nod]])
getDist(Exit[nod]);
Dist[nod]=1+Dist[Exit[nod]];
}
pair<int,int> Qry[2005];
int Fr[300005];
void getSol(int N, int Q, int G[], int cycleSize)
{
for(int i=0; i<=300000; i++)
Fr[i]=0;
for(int i=0; i<Q; i++)
Qry[i+1]={G[i],i+1};
sort(Qry+1,Qry+Q+1);
sort(Dist+1,Dist+N+1);
//Dist[nod]<=Qry[ind] si Dist[nod]%cycleSize==Qry[ind]%cycleSize ca sa pot ajunge in P si nod<=N (o sa ies prin cel mai mare edge)
//daca cycleSize e INF, practic nu se face modulo, lungimile trb sa fie egale (P nu e in niciun ciclu)
int j=1;
for(int i=1; i<=Q; i++)
{
while(j<=N && Dist[j]<=Qry[i].first)
{
if(Dist[j]>=INF)
continue;
Fr[Dist[j]%cycleSize]++;
j++;
}
if(cycleSize<INF)
Sol[Qry[i].second]+=Fr[Qry[i].first%cycleSize];
else if(Qry[i].first<=300000)
Sol[Qry[i].second]+=Fr[Qry[i].first];
}
}
void addEdge(int ind, int x, int y, int N)
{
if(ind==Prim[x])
{
if(ind==Prim[y] && Sec[y])
Exit[x]=N+y;
else
Exit[x]=y;
}
else if(ind==Sec[x])
{
if(ind==Prim[y] && Sec[y])
Exit[N+x]=N+y;
else
Exit[N+x]=y;
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0; i<M; i++)
{
R[i][0]++;
R[i][1]++;
if(!Prim[R[i][0]])
Prim[R[i][0]]=i+1;
else if(!Sec[R[i][0]])
Sec[R[i][0]]=i+1;
if(!Prim[R[i][1]])
Prim[R[i][1]]=i+1;
else if(!Sec[R[i][1]])
Sec[R[i][1]]=i+1;
}
for(int i=0; i<=M; i++)
{
addEdge(i+1,R[i][0],R[i][1],N);
addEdge(i+1,R[i][1],R[i][0],N);
}
for(int i=1; i<=2*N; i++)
Dist[i]=INF;
P++;
Dist[0]=INF;
Viz[0]=1;
//termin in nodul P
Viz[P]=1;
Dist[P]=0;
for(int i=1; i<=2*N; i++)
{
if(!Viz[i])
getDist(i);
}
int cycleSize=1+Dist[Exit[P]]; //dupa ce va ajunge in P va face ciclul respectiv, daca P se afla pe vreun ciclu
getSol(N,Q,G,cycleSize);
//termin in 2*P
for(int i=1; i<=2*N; i++)
{
Dist[i]=INF;
Viz[i]=0;
}
Viz[N+P]=1;
Dist[N+P]=0;
for(int i=1; i<=2*N; i++)
{
if(!Viz[i])
getDist(i);
}
cycleSize=1+Dist[Exit[N+P]];
getSol(N,Q,G,cycleSize);
for(int i=1; i<=Q; i++)
answer(Sol[i]);
}
