#include "garden.h"
#include "gardenlib.h"
#include <vector>
using namespace std;
void count_routes(int n, int m, int p, int R[][2], int q, int G[])
{
vector<int> adj(2 * n, -1), best(n, -1);
for (int i = 0; i < m; ++i)
{
auto [u, v] = R[i];
if (best[u] == -1) best[u] = v;
if (adj[2 * u] == -1) adj[2 * u] = v;
else if (adj[2 * u + 1] == -1) adj[2 * u + 1] = v;
swap(u, v);
if (best[u] == -1) best[u] = v;
if (adj[2 * u] == -1) adj[2 * u] = v;
else if (adj[2 * u + 1] == -1) adj[2 * u + 1] = v;
}
for (int i = 0; i < n; ++i)
{
if (adj[2 * i + 1] == -1) adj[2 * i + 1] = adj[2 * i];
adj[2 * i] *= 2;
adj[2 * i + 1] *= 2;
if (best[adj[2 * i] / 2] == i) ++adj[2 * i];
if (best[adj[2 * i + 1] / 2] == i) ++adj[2 * i + 1];
}
vector<int> d(2 * n, -1);
auto dfs = [&d, &adj](auto self, int v) -> int
{
if (d[v] == -2) return -3;
if (d[v] != -1) return d[v];
d[v] = -2;
d[v] = self(self, adj[v]) + 1;
if (d[v] == -2) return -3;
return d[v];
};
vector<int> result(q);
//2 * p
d[2 * p] = 0;
for (int i = 0; i < 2 * n; ++i) if (d[i] == -1) dfs(dfs, i);
int len = 0;
if (d[adj[2 * p]] > 0) len = d[adj[2 * p]] + 1;
for (int i = 0; i < q; ++i)
{
for (int j = 0; j < n; ++j)
{
if (d[2 * j] >= 0 && G[i] >= d[2 * j])
{
if (len) result[i] += (G[i] - d[2 * j]) % len == 0;
else result[i] += G[i] == d[2 * j];
}
}
}
//2 * p + 1
d = vector<int>(2 * n, -1);
d[2 * p + 1] = 0;
for (int i = 0; i < 2 * n; ++i) if (d[i] == -1) dfs(dfs, i);
len = 0;
if (d[adj[2 * p + 1]] > 0) len = d[adj[2 * p + 1]] + 1;
for (int i = 0; i < q; ++i)
{
for (int j = 0; j < n; ++j)
{
if (d[2 * j] >= 0 && G[i] >= d[2 * j])
{
if (len) result[i] += (G[i] - d[2 * j]) % len == 0;
else result[i] += G[i] == d[2 * j];
}
}
}
for (int i : result) answer(i);
}
