#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int maxn = 3e5 + 5;
int n, f[maxn];
vector<int> g[maxn], adj[maxn];
bool vis[maxn];
int cyc;
void dfs(int r, int v, int d) {
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[maxn], dis[maxn];
solver(int v){
fill(vis, vis + n + n, 0);
fill(dis, dis + n + n, -1);
cyc = 0;
dfs(v, v, 0);
vec.resize(cc = cyc);
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: adj[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 >= maxn ? 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 k[]) {
::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++) adj[f[i]].push_back(i);
solver a(p), b(p + n);
for(int i = 0; i < q; i++) answer(a.get(k[i]) + b.get(k[i]));
}
