#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
const int MAX = 3e5 + 5;
int n, m, p, q;
vector<pii> g[MAX];
int nxt[MAX];
vector<int> G[MAX];
int vis[MAX], cyc[MAX];
int H[MAX][2], sz[2];
void dfs(int node, int h, int t){
vis[node] = 1;
for(int to : G[node]){
if(vis[to]) continue;
dfs(to, h + 1, t);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int QQ[]){
n = N, m = M, p = P, q = Q;
for(int i = 0; i < M; i++){
g[R[i][0]].push_back({i, R[i][1]});
g[R[i][1]].push_back({i, R[i][0]});
}
for(int i = 0; i < n; i++) sort(all(g[i]));
for(int i = 0; i < 2 * n; i++) nxt[i] = -1;
for(int i = 0; i < n; i++){
int j = g[i][0].second;
if(g[j][0].second == i){
nxt[i] = j + n;
if(g[i].size() > 1) nxt[i + n] = g[i][1].second;
else nxt[i + n] = j + n;
}
else nxt[i] = j;
}
for(int i = 0; i < 2 * n; i++){
if(vis[i] || nxt[i] == -1) continue;
int a = i;
while(!vis[a]){
vis[a] = i + 1;
a = nxt[a];
}
if(vis[a] != i + 1) continue;
int b = nxt[a];
cyc[a] = 1;
while(b != a){
cyc[b] = 1;
b = nxt[b];
}
}
for(int i = 0; i < 2 * n; i++){
// cout << i << ' ' << nxt[i] << endl;
if(nxt[i] != -1) G[nxt[i]].push_back(i);
}
if(!cyc[P]){
sz[0] = 1e9;
if(nxt[P] != -1) dfs(P, 0, 0);
}
else{
int a = nxt[P];
sz[0] = 1;
while(a != P){
sz[0]++;
a = nxt[a];
}
fill(vis, vis + MAX, 0);
dfs(P, 0, 0);
}
if(!cyc[P+n]){
sz[1] = 1e9;
if(nxt[P+n] != -1) dfs(P+n, 0, 1);
}
else{
int a = nxt[P+n];
sz[1] = 1;
while(a != P+n){
sz[1]++;
a = nxt[a];
}
fill(vis, vis + MAX, 0);
dfs(P+n, 0, 1);
}
for(int z = 0; z < q; z++){
int k = QQ[z];
int ans = 0;
for(int i = k % sz[0]; i <= min(MAX-1, k); i += sz[0]){
ans += H[i][0];
}
for(int i = k % sz[1]; i <= min(MAX-1, k); i += sz[1]){
ans += H[i][1];
}
answer(ans);
}
}
