#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 3e5 + 5;
vector<int> adj[MXN];
vector<array<int, 2>> g[MXN];
int incyc[MXN], par[MXN];
int used[MXN];
int sz[2] = {0, 0};
void dfs(int a, int f)
{
used[a] = 1;
for (int &v : adj[a])
{
if (used[v] == 2) continue;
if (used[v] == 0)
{
par[v] = a;
dfs(v, f);
}
else
{
int e = a;
while (1)
{
sz[f]++;
incyc[e] = 1;
if (e == v) break;
e = par[e];
}
}
}
used[a] = 2;
}
void add_edge(int u, int v)
{
adj[v].push_back(u);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for (int i = 0; i < M; i++)
{
auto [u, v] = R[i];
g[u].push_back({i, v});
g[v].push_back({i, u});
}
for (int i = 0; i < N; i++)
{
if (g[i].empty()) continue;
sort(g[i].begin(), g[i].end());
int A = g[i][0][1];
if (g[A][0][1] == i) A = A * 2 + 1;
else A = A * 2;
add_edge(2 * i, A);
if (g[i].size() == 1)
{
add_edge(2 * i + 1, A);
continue;
}
A = g[i][1][1];
if (g[A][0][1] == i) A = A * 2 + 1;
else A = A * 2;
add_edge(2 * i + 1, A);
}
dfs(P * 2, 0);
dfs(P * 2 + 1, 1);
int d[2][N * 2], seen[2][N * 2];
for (int i = 0; i < 2; i++)
{
fill(d[i], d[i] + N * 2, -1);
fill(seen[i], seen[i] + N * 2, 0);
queue<int> q;
d[i][P * 2 + i] = 0, q.push(P * 2 + i);
while (!q.empty())
{
int a = q.front();
seen[i][a] |= incyc[a];
q.pop();
for (int &v : adj[a])
{
if (d[i][v] != -1) continue;
d[i][v] = d[i][a] + 1;
seen[i][v] = seen[i][a];
q.push(v);
}
}
}
for (int i = 0; i < Q; i++)
{
int x = G[i], res = 0;
for (int j = 0; j < N; j++)
{
int ok = 0;
for (int l = 0; l < 2; l++)
{
if (d[l][2 * j] == -1) continue;
if (seen[l][2 * j]) ok |= (x - d[l][2 * j]) % sz[l] == 0;
else ok |= d[l][2 * j] == x;
}
res += ok;
}
answer(res);
}
}
