#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);
vector <int> vecA, vecB;
for(int u = 0; u < N; u++)
{
if(distA[u] != INT_MAX)
vecA.push_back(distA[u]);
else if(distB[u] != INT_MAX)
vecB.push_back(distB[u]);
}
sort(vecA.begin(), vecA.end(), greater <int> ());
sort(vecB.begin(), vecB.end(), greater <int> ());
vector <int> perm (Q);
for(int i = 0; i < Q; i++)
perm[i] = i;
sort(perm.begin(), perm.end(),
[&] (const int &i, const int &j)
{
return G[i] < G[j];
});
vector <int> ans (Q);
vector <int> cntA (N * 2, 0);
vector <int> cntB (N * 2, 0);
for(int x = 0; x < Q; x++)
{
int i = perm[x];
while(vecA.empty() == false && vecA.back() <= G[i])
{
cntA[vecA.back() % cycleA]++;
vecA.pop_back();
}
while(vecB.empty() == false && vecB.back() <= G[i])
{
cntB[vecB.back() % cycleB]++;
vecB.pop_back();
}
if(G[i] % cycleA < N * 2)
ans[i] += cntA[G[i] % cycleA];
if(G[i] % cycleB < N * 2)
ans[i] += cntB[G[i] % cycleB];
}
for(int i = 0; i < Q; i++)
answer(ans[i]);
}
