#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 3e5+5;
int n, f[MXN];
vector<int> g[MXN], gg[MXN];
bool vis[MXN];
int cyc;
void dfs(int r, int v, int d = 0) {
vis[v] = 1;
if(!vis[f[v]]) dfs(r, f[v], d+1);
else if(f[v]==r) cyc = d+1;
}
struct solver {
int cc;
vector<vector<int>> vec;
int cnt[MXN];
int dis[MXN];
solver(int v) {
fill(vis, vis + n + n, 0);
cyc = 0;
dfs(v, v);
vec.resize(cc = cyc);
fill(dis, dis+n+n, -1);
memset(cnt, 0, sizeof(cnt));
dis[v] = 0;
if(v<n) cnt[0]++;
queue<int> q;
q.push(v);
if(v<n && cc) vec[0].push_back(0);
while(!q.empty()) {
v = q.front();
q.pop();
for(int u : gg[v]) {
if(dis[u]==-1) {
dis[u] = dis[v]+1;
if(u<n) cnt[dis[u]]++;
q.push(u);
if(u<n && cc) vec[dis[u]%cc].push_back(dis[u]);
}
}
}
}
int get(int k) {
if(!cc) return k>=MXN ? 0 : cnt[k];
return upper_bound(vec[k%cc].begin(), vec[k%cc].end(), k)-vec[k%cc].begin();
}
};
void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
::n = n;
for(int i = 0; i < m; i++) {
g[R[i][0]].push_back(R[i][1]);
g[R[i][1]].push_back(R[i][0]);
}
for(int i = 0; i < n; i++) {
f[i] = g[i][0] + (g[g[i][0]][0] == i ? n : 0);
if(g[i].size() == 1) f[i + n] = f[i];
else f[i + n] = g[i][1] + (g[g[i][1]][0] == i ? n : 0);
}
for(int i = 0; i < n + n; i++) gg[f[i]].push_back(i);
solver A(P), B(P + n);
for(int i = 0; i < Q; i++) answer(A.get(G[i]) + B.get(G[i]));
}
