#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define DIMN 150010
using namespace std;
int f[2][DIMN] , taken[2][DIMN] , poz[2][DIMN] , taken_2[2][DIMN];
int dist[2][DIMN] , far[2][DIMN] , sol[2010];
vector < pair <int,int> > tt[2][DIMN];
pair <int , int> urm[2][DIMN];
int prm[DIMN] , doi[DIMN];
vector <int> v[DIMN];
deque <pair <int,int> > dq;
void calcul (int state , int curr , int n , int q , int g[]){
int si , ci , dis , i , new_state , vecin , len1;
for (i = 1 ; i <= n ; i++){
dist[0][i] = dist[1][i] = taken[0][i] = taken[1][i] = 0;
}
si = state;
ci = curr;
dis = 0;
while (!taken[state][curr]){
taken[state][curr] = ++dis;
new_state = urm[state][curr].first;
vecin = urm[state][curr].second;
state = new_state;
curr = vecin;
}
if (state == si && curr == ci){ /// exista ciclu care il contine pe 0 , p
len1 = dis; /// in muchii
for (i = 1 ; i <= n ; i++){
if (taken[0][i]){
dist[0][i] = (dis - taken[0][i] + 1) % dis;
dq.push_back(make_pair(0 , i));
}
if (taken[1][i]){
dist[1][i] = (dis - taken[1][i] + 1) % dis;
dq.push_back(make_pair(1 , i));
}
}
while (!dq.empty()){
state = dq.front().first;
curr = dq.front().second;
dq.pop_front();
if (state == 0){
for (i = 0 ; i < q ; i++){
if (dist[state][curr] % len1 == g[i] % len1 && dist[state][curr] <= g[i]){
sol[i]++;
//if (si == 1)
// printf ("%d %d\n" , state , curr);
}
}
}
for (i = 0 ; i < tt[state][curr].size() ; i++){
new_state = tt[state][curr][i].first;
vecin = tt[state][curr][i].second;
if ( taken[new_state][vecin] == 0 ){
dist[new_state][vecin] = 1 + dist[state][curr];
dq.push_back(make_pair(new_state , vecin));
}
}
}
}
else { /// stare curr nu face parte din ciclu
state = si;
curr = ci;
dq.push_back(make_pair(state , curr));
dist[state][curr] = 1;
while (!dq.empty()){
state = dq.front().first;
curr = dq.front().second;
dq.pop_front();
if (state == 0){
for (i = 0 ; i < q ; i++){
if (dist[state][curr] - 1 == g[i])
sol[i]++;
}
}
for (i = 0 ; i < tt[state][curr].size() ; i++){
new_state = tt[state][curr][i].first;
vecin = tt[state][curr][i].second;
dist[new_state][vecin] = 1 + dist[state][curr];
dq.push_back(make_pair(new_state , vecin));
}
}
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
int i , curr , state , vecin , new_state , pc;
p++;
for (i = 0 ; i < m ; i++){
r[i][0]++;
r[i][1]++;
}
for (i = 1 ; i <= n ; i++){
prm[i] = doi[i] = -1;
poz[0][i] = poz[1][i] = 0;
}
for (i = 0 ; i < m ; i++){
if (prm[r[i][0]] == -1)
prm[r[i][0]] = r[i][1];
else if (doi[r[i][0]] == -1)
doi[r[i][0]] = r[i][1];
if (prm[r[i][1]] == -1)
prm[r[i][1]] = r[i][0];
else if (doi[r[i][1]] == -1)
doi[r[i][1]] = r[i][0];
}
/// daca in nod ajungi pe muchia prm[nod] , o iei pe doi[nod], daca ea exista
/// state = 0, esti libera sa o iei pe prm
for (i = 1 ; i <= n ; i++){
curr = i;
state = 0;
pc = 1;
while (!poz[state][curr]){
poz[state][curr] = pc;
pc++;
if (state == 0 || doi[curr] == -1){
vecin = prm[curr];
if (prm[vecin] == curr && doi[vecin] != -1)
new_state = 1;
else new_state = 0;
}
else {
vecin = doi[curr];
if (prm[vecin] == curr && doi[vecin] != -1)
new_state = 1;
else new_state = 0;
}
/// din state, curr ----> new_state , vecin
urm[state][curr] = make_pair(new_state , vecin);
tt[new_state][vecin].push_back(make_pair(state , curr));
//printf ("%d %d %d %d\n" , state , curr , new_state , vecin);
state = new_state;
curr = vecin;
}
}
calcul (0 , p , n , q , g);
calcul (1 , p , n , q , g);
for (i = 0 ; i < q ; i++)
answer(sol[i]);
}
