#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(r==v && d) {
cyc = d;
return;
}
if(!vis[f[v]]) dfs(r, f[v], 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 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] = g[i][0]+(g[g[i][0]][0]==i && g[g[i][0]].size()>1 ? n : 0);
else f[i+n] = g[i][1]+(g[g[i][1]][0]==i && g[g[i][1]].size()>1 ? 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]));
}
