#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
/*****************************************/
//just have to implement
#define pi pair<int,int>
#define pb insert
#define ll long long
#define f first
#define s second
const int maxn = 3e5 + 5;
const int logn = 1;
//int level[maxn];
set<int> rgraph[maxn];
bool vis[maxn];
int up[maxn][logn];
int distroot[maxn][2];
int cycle[2];
void dfs(int root, int node, int dist){
vis[node] = true;
distroot[node][root%2] = dist;
for(int adj : rgraph[node]){
if(adj == root){
cycle[root%2] = dist +1;
}
if(vis[adj]) continue;
dfs(root, adj, dist + 1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
memset(up, -1, sizeof(up));
for(int i =0; i<M; i++){
int a = 2* R[i][0];
int b = 2* R[i][1];
if(up[a][0] == -1){
if( up[b][0] == -1){
up[a][0] = b+1;
up[a+1][0] = b+1;
rgraph[b+1].pb(a);
rgraph[b+1].pb(a+1);
}
else{
up[a][0] = b;
up[a+1][0] = b;
rgraph[b].pb(a);
rgraph[b].pb(a+1);
}
}
else if(up[a][0] == up[a+1][0]){
rgraph[up[a+1][0]].erase(a+1);
if(up[b][0] == -1)
{
up[a+1][0] = b+1;
rgraph[b+1].pb(a+1);
}
else
{
up[a+1][0] = b;
rgraph[b].pb(a+1);
}
}
if(up[b][0] == -1){
if(up[a][0] == b +1){
up[b][0] = a+1;
up[b+1][0] = a+1;
rgraph[a+1].pb(b);
rgraph[a+1].pb(b+1);
}
else{
up[b][0] = a;
up[b+1][0]= a;
rgraph[a].pb(b);
rgraph[a].pb(b+1);
}
}
else if(up[b][0] == up[b+1][0]){
rgraph[up[b+1][0]].erase(b+1);
if(up[a][0] == b)
{
up[b+1][0] = a+1;
rgraph[a+1].pb(b+1);
}
else
{
up[b+1][0] = a;
rgraph[a].pb(b+1);
}
}
}
/*
for(int i =0; i< N; i++){
int a = up[i*2][0];
int b= up[i*2 +1][0];
if(a % 2== 1){
cout << i <<" -> "<<a/2<<"'\n";
}
else{
cout << i <<" -> "<<a/2<<"\n";
}
if(b % 2== 1){
cout << i <<"' -> "<<b/2<<"'\n";
}
else{
cout << i <<"' -> "<<b/2<<"\n";
}
}
for(int i =1;i<=5; i++){
int res = jump(0, i);
if(res % 2 == 1)
cout << "0 + "<<i<<" -> "<<res/2<<"'\n";
else
cout << "0 + "<<i<<" -> "<<res/2<<"\n";
}
*/
/*for(int i =0; i<N; i++){
cout << i <<": ";
for(int adj : rgraph[2*i])
cout << adj <<", ";
cout <<endl;
cout << i<<"': ";
for(int adj : rgraph[2*i +1])
cout <<adj<<", ";
cout <<endl;
}*/
for(int i =0; i< maxn; i++ )
distroot[i][0] = distroot[i][1] = -1;
cycle[0] = cycle[1] = -1;
dfs(2*P, 2*P, 0);
dfs(2*P+1, 2*P +1, 0);
/*cout << cycle[0]<<", "<<cycle[1]<<":\n";
for(int i=0; i<N; i++){
cout <<i<<": "<< distroot[i*2][0]<<", "<<distroot[i*2][1]<<endl;
}*/
for(int i =0; i<Q; i++){
ll ans = 0;
for(int j =0; j<N; j++){
if(distroot[j *2][0] != -1){
if(distroot[j*2][0] == G[i])
{
ans++;
}
else if(cycle[0]!= -1){
if( (G[i] - distroot[j*2][0]) % cycle[0] == 0){
ans++;
}
}
}
else if(distroot[j*2][1] != -1){
if(distroot[j*2 ][1] == G[i])
ans++;
else if(cycle[1] != -1)
if((G[i] - distroot[j*2][1]) % cycle[1] == 0)
ans++;
}
}
answer(ans);
}
}
/******************************************/
