#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define sep " "
#define SZ(x) int((x).size())
const int MAXN = 3e5 + 10;
int n , m , p , nxt[MAXN] , V[MAXN] , U[MAXN] , comp[MAXN] , mark[MAXN] , H[MAXN] , ind[MAXN] , valid[MAXN] , first[MAXN];
vector<int> E[MAXN] , vec , cycle[MAXN] , adj[MAXN] , par[MAXN];
void PreDFS(int v){
mark[v] = 1;
if(!mark[nxt[v]]){
PreDFS(nxt[v]);
}
vec.push_back(v);
}
void DFS(int v , int cmp , int root , int h = 0){
if(valid[v]) vec.push_back(h);
par[v] = vec;
H[v] = h; comp[v] = cmp; ind[v] = root;
for(int u : adj[v]){
if(comp[u] != -1) continue;
DFS(u , cmp , root , h + 1);
}
if(valid[v]) vec.pop_back();
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
fill(comp , comp + MAXN , -1);
fill(first , first + MAXN , -1);
n = N; m = M; p = P;
for(int i = 0 ; i < m ; i++){
V[i] = R[i][0]; U[i] = R[i][1];
E[V[i]].push_back(2 * i);
E[U[i]].push_back(2 * i + 1);
if(first[V[i]] == -1){
first[V[i]] = 2 * i + 1;
}
if(first[U[i]] == -1){
first[U[i]] = 2 * i;
}
}
for(int i = 0 ; i < n ; i++){
for(int j = 1 ; j < SZ(E[i]) ; j++){
nxt[E[i][j]] = (E[i][0] ^ 1);
}
nxt[E[i][0]] = (E[i][1 % SZ(E[i])] ^ 1);
}
for(int i : E[p]){
valid[i] = 1;
}
for(int i = 0 ; i < 2 * m ; i++){
adj[nxt[i]].push_back(i);
// cout << i << sep << nxt[i] << endl;
}
for(int i = 0 ; i < 2 * m ; i++){
if(comp[i] != -1) continue;
vec.clear();
PreDFS(i);
int v = vec[0];
while(comp[v] == -1){
comp[v] = i;
cycle[i].push_back(v);
v = nxt[v];
}
for(int j = 0 ; j < SZ(cycle[i]) ; j++){
vec.clear();
DFS(cycle[i][j] , i , j , 0);
}
}
for(int i = 0 ; i < Q ; i++){
int k = G[i] - 1 , ans = 0;
for(int j = 0 ; j < n ; j++){
int e = first[j];
if(H[e] <= k){
int x = cycle[comp[e]][(k - H[e] + ind[e]) % SZ(cycle[comp[e]])];
ans += valid[x];
// cout << j << sep << e << sep << x << sep << valid[x] << endl;
}
else{
// cout << "Debug " << j << endl;
for(int x : par[e]){
if(H[e] - x == k){
ans++;
}
}
}
}
// cout << ans << endl;
answer(ans);
}
}
