#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 150001;
vector<int> adj[N];
int cNum = 1;
int cSize[N][2];
int best[N][2];
int dist[N][2];
vector<array<int, 2>> st;
int onSt[N][2];
int p;
void dfs(int node, int type)
{
st.push_back({node, type});
onSt[node][type] = 1;
array<int, 2> next = {-1, -1};
int other = -1;
int eVal = -1;
if (type == 0)
{
other = adj[node][0];
eVal = best[node][0];
} else
{
other = adj[node][1];
eVal = best[node][1];
}
if (best[other][0] == eVal && best[other][1] != 0)
{
next = {other, 1};
} else
{
next = {other, 0};
}
if (cSize[next[0]][next[1]])
{
cSize[node][type] = cSize[next[0]][next[1]];
if (dist[next[0]][next[1]] == -1) dist[node][type] = -1;
else dist[node][type] = dist[next[0]][next[1]] + 1;
} else if (onSt[next[0]][next[1]])
{
auto it = st.rend();
int siz = 0;
int good = -1;
int cdist = 0;
while (*it != next)
{
siz++;
array<int, 2> ar1 = {p, 0};
array<int, 2> ar2 = {p, 1};
if (*it == ar1 || *it == ar2)
{
good = cdist;
}
cdist++;
it++;
}
siz++;
if (good != -1)
{
dist[node][type] = siz - cdist;
cSize[node][type] = siz;
}
} else
{
dfs(next[0], next[1]);
cSize[node][type] = cSize[next[0]][next[1]];
if (dist[next[0]][next[1]] == -1) dist[node][type] = -1;
else dist[node][type] = dist[next[0]][next[1]] + 1;
}
if (node == p) dist[node][type] = 0;
st.pop_back();
onSt[node][type] = 0;
}
void count_routes(int n, int m, int pa, int R[][2], int Q, int G[])
{
p = pa;
for (int i = 0; i < m; i++)
{
for (int j = 0; j <= 1; j++)
{
if (best[R[i][j]][0] == 0) best[R[i][j]][0] = i + 1;
else if (best[R[i][j]][1] == 0) best[R[i][j]][1] = i + 1;
}
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= 1; j++) dist[i][j] = -1;
}
for (int i = 0; i < n; i++)
{
if (!cSize[i][0]) dfs(i, 0);
}
for(int i=0; i<Q; i++)
{
int sum = 0;
int cdist = G[i];
for (int j = 0; j < n; j++)
{
if (dist[j][0] != -1)
{
if (dist[j][0] == cdist) sum++;
else if (cSize[j][0] && cdist > dist[j][0] && dist[j][0] % cSize[j][0] == cdist % cSize[j][0])
{
sum++;
}
}
}
answer(sum);
}
}
