#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
int n, m, p, deg[MAXN], F[MAXN], dist[2][MAXN], cyc[2];
vector<int> adj[MAXN];
bool vis[MAXN];
inline void add_edge(int u, int v) {
F[u] = v;
adj[v].push_back(u);
}
inline void add(int u, int v) {
if (deg[u] > 1) return;
if (deg[u] == 0) {
if (deg[v] == 0) add_edge(u << 1 | 1, v << 1);
else add_edge(u << 1 | 1, v << 1 | 1);
} else {
if (deg[v] == 0) add_edge(u << 1, v << 1);
else add_edge(u << 1, v << 1 | 1);
}
}
void dfs(int v, int len, int ind) {
vis[v] = true;
dist[ind][v] = len;
for (int u : adj[v]) {
if (vis[u]) cyc[ind] = len;
else
dfs(u, len + 1, ind);
}
}
inline bool f(int ind, int v, int k) {
if (!dist[ind][v]) return false;
k -= dist[ind][v] - 1;
if (k == 0) return true;
if (k < 0) return false;
return cyc[ind] && k % cyc[ind] == 0;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N, m = M, p = P;
p++;
for (int i = 0; i < m; i++) {
int u = R[i][0], v = R[i][1];
u++;
v++;
add(u, v);
add(v, u);
deg[u]++;
deg[v]++;
}
for (int v = 1; v <= n; v++)
if (!F[v << 1])
add_edge(v << 1, F[v << 1 | 1]);
dfs(p << 1, 1, 0);
memset(vis, false, sizeof vis);
dfs(p << 1 | 1, 1, 1);
for (int i = 0; i < Q; i++) {
int ans = 0;
for (int v = 1; v <= n; v++)
ans += (f(0, v << 1 | 1, G[i]) || f(1, v << 1 | 1, G[i]));
answer(ans);
}
}
