#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 150000, MAXL = 30;
int par[2*MAXN], parF[MAXN], parS[MAXN], P1, P2, length = -1, dis1[MAXN], dis2[MAXN];
vector<int> adj[2*MAXN];
bool b1 = false, b2 = false;
void dfs1(int s, int e, int d){
if(s == P1 and e != -1){
length = d;
b1 = true;
return;
}
dis1[s] = d;
for(auto u : adj[s]){
dfs1(u, s, d + 1);
}
}
void dfs2(int s, int e, int d){
if(s == P2 and e != -1){
length = d;
b2 = true;
return;
}
dis2[s] = d;
for(auto u : adj[s]){
dfs2(u, s, d + 1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
P1 = P;
P2 = P + N;
for(int i = 0; i < M; i++){
adj[R[i][0]].pb(R[i][1]);
adj[R[i][1]].pb(R[i][0]);
}
for(int i = 0; i < N; i++){
if(adj[i].size() == 1) adj[i].pb(adj[i][0]);
parF[i] = adj[i][0];
parS[i] = adj[i][1];
adj[i].clear();
}
for(int i = 0; i < N; i++){
if(i == parF[parF[i]]){
par[i] = parF[i] + N;
par[parF[i]] = i + N;
}
else{
par[i] = parF[i];
}
if(i == parF[parS[i]]){
par[i + N] = parS[i] + N;
}
else{
par[i + N] = parS[i];
}
}
for(int i = 0; i < 2*N; i++){
adj[par[i]].pb(i);
}
dfs1(P1, -1, 0);
dfs2(P2, -1, 0);
for(int k = 0; k < Q; k++){
int K = G[k], ans = 0;
for(int i = 0; i < N; i++){
int X = K;
if(b1 == true){
X -= dis1[i];
if(X%length == 0) ans++;
}
else{
if(dis1[i] == X) ans++;
}
X = K;
if(b2 == true){
X -= dis2[i];
if(X%length == 0) ans++;
}
else{
if(dis2[i] == X) ans++;
}
}
answer(ans);
}
}
