#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
using namespace std;
const int N = 1e6 + 20;
vector <pair<int, int> > g1[N][2];
int mx[N][2], c[2];
int n, m, p, q;
int d[2][N][2], col[N][2];
void dfs(int v, int x, int lil)
{
col[v][x] = 1;
int x1, v1;
v1 = mx[v][x];
if(mx[v1][0] == v) x1 = 1;
else x1 = 0;
if(!col[v1][x1]) dfs(v1,x1,lil + 1);
else
{
if(v1 == p && x1 == m) c[m] = lil;
else return;
}
}
void bfs(int v, int xx)
{
queue <pair<int, int> > q;
d[xx][v][xx] = 1;
q.push(MP(v, xx));
while(!q.empty())
{
int v = q.front().fr, x = q.front().sc;
q.pop();
for(auto p : g1[v][x])
if(!d[xx][p.fr][p.sc]) d[xx][p.fr][p.sc] = d[xx][v][x] + 1, q.push(p);
}
}
int s(int d, int c, int g)
{
d--;
if(g < d || d < 0) return 0;
if(g == d) return 1;
if(c == 0) return 0;
if((g - d) % c == 0) return 1;
return 0;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n=N,m=M,p=P,q=Q;
for (int i = 0; i < n; i++) mx[i][0] = -1;
for(int i = m - 1; i >= 0; i--)
{
int a = R[i][0], b = R[i][1];
mx[a][1] = mx[a][0], mx[b][1] = mx[b][0];
mx[a][0] = b, mx[b][0] = a;
if(mx[a][1] == -1) mx[a][1] = b;
if(mx[b][1] == -1) mx[b][1] = a;
}
for (int i = 0; i < n; i++)
{
//cout << mx[i][0] << " " << mx[i][1] << endl;
int v = mx[i][0];
if(mx[v][0] == i) g1[v][1].ad(MP(i, 0));
else g1[mx[i][0]][0].ad(MP(i, 0));
if(mx[mx[i][1]][0] == i) g1[mx[i][1]][1].ad(MP(i, 1));
else g1[mx[i][1]][0].ad(MP(i, 1));
}
/*
for (int i = 0; i < n; i++)
{
for(auto p : g1[i][0]) cout << p.fr << p.sc << " ";
cout << " ";
for(auto p : g1[i][1]) cout << p.fr << p.sc << " ";
cout << endl;
}*/
m=0; dfs(p, 0, 1);
for (int i = 0; i < n; i++) col[i][0] = col[i][1] = 0;
m=1; dfs(p, 1, 1);
bfs(p, 0); bfs(p, 1);
//for (int i = 0; i < n; i++) cout << d[0][i][0] << " " << d[1][i][0] << endl;
for (int i = 0; i < q; i++)
{
int ret = 0;
for(int j = 0; j < n; j++)
ret += s(d[0][j][0], c[0], G[i]) + s(d[1][j][0], c[1], G[i]);
answer(ret);
}
//for (int i = 0; i < n; i++) cout << d[1][i][0] << " " << d[1][i][1] << endl;
}
