/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "garden.h"
using namespace std;
typedef long long ll;
void answer (int x);
void count_routes (int N, int M, int P, int R[][2], int Q, int G[])
{
vector <vector <int>> adj (N);
for(int i = 0; i < M; i++)
{
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
vector <int> edge (N * 2);
for(int u = 0; u < N; u++)
{
edge[u] = adj[u][0];
if(adj[edge[u]][0] == u)
edge[u] += N;
}
for(int u = 0; u < N; u++)
{
if((int) adj[u].size() >= 2)
edge[N + u] = adj[u][1];
else
edge[N + u] = adj[u][0];
if(adj[edge[N + u]][0] == u)
edge[N + u] += N;
}
vector <vector <int>> rev (N * 2);
for(int u = 0; u < N * 2; u++)
rev[edge[u]].push_back(u);
function <void (int, vector <int> &, int&)> bfs = [&] (int start, vector <int> &dist, int &cycle)
{
dist = vector <int> (N * 2, INT_MAX);
queue <int> q;
q.push(start);
dist[start] = 0;
while(q.empty() == false)
{
int u = q.front();
q.pop();
for(int v : rev[u])
if(dist[v] == INT_MAX)
{
dist[v] = dist[u] + 1;
q.push(v);
}
}
cycle = 0;
vector <bool> seen (N * 2, false);
int u = start;
while(seen[u] == false)
{
cycle++;
seen[u] = true;
u = edge[u];
}
if(u != start || cycle == 1)
cycle = INT_MAX;
};
vector <int> distA, distB;
int cycleA, cycleB;
bfs(P, distA, cycleA);
bfs(N + P, distB, cycleB);
for(int i = 0; i < Q; i++)
{
int K = G[i];
int cnt = 0;
for(int i = 0; i < N; i++)
{
if(distA[i] <= K && (distA[i] - K) % cycleA == 0)
cnt++;
if(distB[i] <= K && (distB[i] - K) % cycleB == 0)
cnt++;
}
answer(cnt);
}
}
