#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
int i, t;
};
const int N = 3e3 + 42, Q = 2e3 + 10, INF = 2e9;
bool b[N][2];
Node nex[N][2];
vector<int> adj[N];
vector<Node> pre[N][2];
int n, m, fin, q, step[Q], occ[N][2], arc[N], cycle[2], dist[N][2][2];
void BFS(int k) {
queue<Node> q;
q.push({fin, k});
dist[fin][k][k] = 0;
while(!q.empty()) {
Node act = q.front();
q.pop();
for(Node next : pre[act.i][act.t]) {
if(dist[next.i][next.t][k] == INF) {
dist[next.i][next.t][k] = dist[act.i][act.t][k] + 1;
q.push(next);
}
}
}
}
void count_routes(int N_, int M_, int P_, int R[][2], int Q_, int G[]) {
n = N_, m = M_, fin = P_, q = Q_;
for(int i = 0; i < m; i++)
arc[i] = R[i][0] + R[i][1];
for(int i = 0; i < m; i++) {
if(adj[R[i][0]].size() < 2) {
adj[R[i][0]].push_back(i);
}
if(adj[R[i][1]].size() < 2) {
adj[R[i][1]].push_back(i);
}
}
for(int i = 0; i < n; i++)
if(adj[i].size() == 1)
adj[i].push_back(adj[i][0]);
for(int i = 0; i < n; i++)
for(int j = 0; j < 2; j++) {
int s = arc[adj[i][j]] - i;
if(adj[i][j] == adj[s][0]) {
nex[i][j] = {s, 1};
pre[s][1].push_back({i, j});
} else {
nex[i][j] = {s, 0};
pre[s][0].push_back({i, j});
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
dist[i][j][k] = INF;
int i = fin, j = 0, nb = 0;
cycle[0] = cycle[1] = -1;
do {
nb++;
b[i][j] = true;
Node next = nex[i][j];
i = next.i;
j = next.t;
} while(!b[i][j]);
if(i == fin && j == 0) {
cycle[0] = nb;
}
for(int i = 0; i < n; i++)
b[i][0] = b[i][1] = false;
i = fin, j = 1, nb = 0;
do {
nb++;
b[i][j] = true;
Node next = nex[i][j];
i = next.i;
j = next.t;
} while(!b[i][j]);
if(i == fin && j == 1) {
cycle[1] = nb;
}
BFS(0);
BFS(1);
for(int k = 0; k < 2; k++)
if(cycle[k] != -1) {
for(int i = 0; i < n; i++)
if(dist[i][0][k] != INF)
occ[dist[i][0][k] % cycle[k]][k]++;
} else {
for(int i = 0; i < n; i++)
if(dist[i][0][k] != INF)
occ[dist[i][0][k]][k]++;
}
for(int i = 0; i < q; i++) {
int ans = 0;
if(cycle[0] != -1) {
ans += occ[G[i] % cycle[0]][0];
} else {
if(G[i] < N) {
ans += occ[G[i]][0];
}
}
if(cycle[1] != -1) {
ans += occ[G[i] % cycle[1]][1];
} else {
if(G[i] < N) {
ans += occ[G[i]][1];
}
}
answer(ans);
}
}
