#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 150000
lli n,m,p,a,b,ini,res;
lli cont[MAX+2],uno[MAX+2];
vector<lli> hijos[MAX*3];
lli dist[2][MAX*3];
lli tam[2],visitados[2][MAX*3],k;
stack<lli> pila;
vector<lli> ciclo;
void asigna(lli x, lli y) {
if (cont[x] == 0) {
if (cont[y] == 0 && uno[y] > 1) hijos[y+n].push_back(x);
else hijos[y].push_back(x);
}
else if (cont[x] == 1) {
if (cont[y] == 0 && uno[y] > 1) hijos[y+n].push_back(x+n);
else hijos[y].push_back(x+n);
}
else return;
}
void dfs(lli pos, lli dis, lli id) {
visitados[id][pos] = 1;
dist[id][pos] = dis;
for (auto h : hijos[pos]) {
if (visitados[id][h] == 1) tam[id] = dis+1;
else dfs(h,dis+1,id);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P;
rep(i,0,m-1) {
a = R[i][0];
b = R[i][1];
uno[a]++;
uno[b]++;
}
rep(i,0,m-1) {
a = R[i][0];
b = R[i][1];
asigna(a,b);
asigna(b,a);
cont[a]++;
cont[b]++;
}
dfs(p,0,0);
dfs(p+n,0,1);
rep(q,0,Q-1) {
res = 0;
k = G[q];
rep(i,0,n-1) {
rep(j,0,1) {
//debugsl(j);
//debugsl(i);
//debug(dist[j][i]);
if (visitados[j][i] == 0) continue;
a = k - dist[j][i];
if (a == 0) {res++; break;}
else if (a > 0) {
if (tam[j] > 0 && (a%tam[j]) == 0) {res++; break;}
}
}
}
answer(res);
}
}
