#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 3e5 + 10;
int n, m, q, cnt, mn[N], M[N], C[N], out[N], dp[2][N]; vector<int> adj[N];
int cycDFS(int v) {
if (C[v]) return 0;
if (M[v]) {
C[v] = 1;
return 1;
}
M[v] = 1;
int u = out[v];
return C[v] = cycDFS(u);
}
void BFS(int st) {
int *pd = dp[st >= n];
fill(pd, pd + N, 1e9);
pd[st] = 0; queue<int> Q; Q.push(st);
while (SZ(Q)) {
int v = Q.front(); Q.pop();
for (int u : adj[v])
if (pd[u] > pd[v] + 1)
pd[u] = pd[v] + 1, Q.push(u);
}
}
inline int check(int p, int v, int x) {
if (dp[p >= n][v] > x) return 0;
return !((x - dp[p >= n][v]) % cnt);
}
void count_routes(int _n, int _m, int P, int R[][2], int _q, int G[]) {
n = _n, m = _m, q = _q;
fill(mn, mn + N, 1e9);
for (int i = 0; i < m; i++) {
adj[R[i][0]].push_back(i), mn[R[i][0]] = min(mn[R[i][0]], i);
adj[R[i][1]].push_back(i), mn[R[i][1]] = min(mn[R[i][1]], i);
}
for (int i = 0; i < n * 2; i++) {
if (i >= n) {
int v = R[mn[i - n]][0] ^ (i - n) ^ R[mn[i - n]][1];
if (mn[i - n] == mn[v]) out[i] = v;
else out[i] = v + n;
} else {
int sec = -1;
for (int id : adj[i])
if (id != mn[i]) { sec = id; break; }
if (!~sec) sec = mn[i];
int v = R[sec][0] ^ i ^ R[sec][1];
if (sec == mn[v]) out[i] = v;
else out[i] = v + n;
}
}
for (int i = 0; i < n; i++)
adj[i] = {};
for (int i = 0; i < 2 * n; i++)
adj[out[i]].push_back(i);
cycDFS(0);
for (int i = 0; i < 2 * n; i++)
cnt += C[i];
BFS(P), BFS(P + n);
for (int _ = 0; _ < q; _++) {
int x = G[_], f = 0;
for (int i = n; i < 2 * n; i++) {
f += (check(P, i, x) || check(P + n, i, x));
}
answer(f);
}
}
