#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int bfs(int s, const vector< vector<int> > &g, vector<int> &dist) {
int n = (int) g.size();
dist.assign(n, -1); dist[s] = 0;
queue<int> q; q.push(s);
int c = -1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
if (v == s) {
c = dist[u] + 1;
}
}
}
return c;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
vector< set<int> > mn(N);
for (int i = 0; i < M; i++) {
mn[R[i][0]].insert(i);
mn[R[i][1]].insert(i);
}
vector< vector<int> > g(2 * N);
for (int i = 0; i < N; i++) {
int idx = *mn[i].begin();
int other = R[idx][0];
if (other == i) other = R[idx][1];
if (idx == *mn[other].begin() && (int) mn[other].size() > 1) g[2 * other + 1].push_back(2 * i);
else g[2 * other].push_back(2 * i);
if ((int) mn[i].size() == 1) continue;
idx = *next(mn[i].begin());
other = R[idx][0];
if (other == i) other = R[idx][1];
if (idx == *mn[other].begin() && (int) mn[other].size() > 1) g[2 * other + 1].push_back(2 * i + 1);
else g[2 * other].push_back(2 * i + 1);
}
vector<int> dist1, dist2;
int c1 = bfs(2 * P, g, dist1);
int c2 = bfs(2 * P + 1, g, dist2);
for (int i = 0; i < Q; i++) {
int cnt = 0;
for (int u = 0; u < 2 * N; u += 2) {
bool b1 = dist1[u] != -1;
if (c1 == -1) b1 = b1 && dist1[u] == G[i];
else b1 = b1 && dist1[u] <= G[i] && (G[i] - dist1[u]) % c1 == 0;
bool b2 = dist2[u] != -1;
if (c2 == -1) b2 = b2 && dist2[u] == G[i];
else b2 = b2 && dist2[u] <= G[i] && (G[i] - dist2[u]) % c2 == 0;
if (b1 || b2) cnt++;
}
answer(cnt);
}
}
