#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define arr array<int, 2>
vector<arr> graph;
vector<arr> vis;
vector<arr> dist1;
vector<arr> dist2;
int starti, starts;
int next(int i, int state)
{
if (state==0)
{
int b = 0;
if (i==graph[graph[i][0]][0]) b= 1;
return b;
}
else
{
int b = 0;
if (i==graph[graph[i][1]][0]) b= 1;
return b;
}
}
int fcycle(int i, int state)
{
if (vis[i][state])
{
if (i == starti && state == starts) return 0;
else return 2*-1e9;
}
vis[i][state] = 1;
if (state==0) return fcycle(graph[i][0], next(i,state))+1;
else return fcycle(graph[i][1], next(i,state))+1;
}
int dfs1(int i, int state)
{
if (vis[i][state]) return dist1[i][state];
vis[i][state] = 1;
if (state==0) dist1[i][state] = dfs1(graph[i][0], next(i,state))+1;
else dist1[i][state] = dfs1(graph[i][1], next(i,state))+1;
return dist1[i][state];
}
int dfs2(int i, int state)
{
if (vis[i][state]) return dist2[i][state];
vis[i][state] = 1;
if (state==0) dist2[i][state] = dfs2(graph[i][0], next(i,state))+1;
else dist2[i][state] = dfs2(graph[i][1], next(i,state))+1;
return dist2[i][state];
}
const int K = 2*1e9;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
graph.assign(N, {-1, -1});
dist1.assign(N, {K, K});
dist2.assign(N, {K, K});
for (int i = 0; i < M; i++)
{
int r1 = R[i][0];
int r2 = R[i][1];
if (graph[r1][0]==-1) graph[r1][0] = r2;
else if (graph[r1][1]==-1) graph[r1][1] = r2;
if (graph[r2][0]==-1) graph[r2][0] = r1;
else if (graph[r2][1]==-1) graph[r2][1] = r1;
}
for (int i = 0; i < N; i++)
{
if (graph[i][1]==-1) graph[i][1] = graph[i][0];
}
vis.assign(N, {0,0});
starti = P;
starts = 0;
int f = fcycle(starti, starts);
vis.assign(N, {0,0});
starts = 1;
int s = fcycle(starti, starts);
vis.assign(N, {0,0});
dist1[P][0] = 0;
vis[P][0] = 1;
for (int i = 0; i < N; i++)
{
dfs1(i, 0);
}
vis.assign(N, {0,0});
dist2[P][1] = 0;
vis[P][1] = 1;
for (int i = 0; i < N; i++)
{
dfs2(i, 0);
}
for (int i = 0; i < Q; i++)
{
int ans=0;
for (int j = 0; j < N; j++)
{
int b = 0;
if (G[i]-dist1[j][0]>=0 && (G[i]-dist1[j][0])%f==0) b=1;
if (G[i]-dist2[j][0]>=0 && (G[i]-dist2[j][0])%s==0) b=1;
ans +=b;
}
answer(ans);
//cout << ans;
}
}
/*
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n, m, p, q;
cin >> n >> m >> p >> q;
int R[m][2];
int G[q];
for (int i = 0; i < m; i++) cin >> R[i][0] >> R[i][1];
for (int i = 0; i < q; i++) cin >> G[i];
count_routes(n, m, p, R, q, G);
return 0;
}
*/
