#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <tuple>
using namespace std;
const int N = 3e5 + 1, INF = 1e9+1;
int n, p, q, res[N], d[N];
vector<int> g[N], cycle;
vector<pair<int, int>> init_g[N];
int cycle_size;
bool mark[N];
void dfs(int u) {
mark[u] = true;
for(int v: g[u]) {
if(!mark[v]) {
d[v] = d[u] + 1;
dfs(v);
} else if(v == p) cycle_size = d[u] + 1;
}
}
void calc() {
fill(mark, mark+2*n, 0);
fill(d, d+2*n, 0);
cycle_size = 0;
dfs(p);
}
int solve(int len) {
int ret = 0;
if(cycle_size) {
for(int i = 0; i < n; i++) if(mark[i])
ret += d[i] <= len && (len - d[i]) % cycle_size == 0;
} else {
for(int i = 0; i < n; i++) if(mark[i])
ret += d[i] == len;
}
return ret;
}
void count_routes(int _n, int m, int _p, int _e[][2], int _q, int len[]) {
n = _n, p = _p, q = _q;
for(int i = 0; i < m; i++) {
if(init_g[_e[i][0]].size() < 2)
init_g[_e[i][0]].emplace_back(_e[i][1], i);
if(init_g[_e[i][1]].size() < 2)
init_g[_e[i][1]].emplace_back(_e[i][0], i);
}
for(int i = 0; i < n; i++) if(init_g[i].size() == 1) init_g[i].push_back(init_g[i][0]);
for(int u = 0; u < n; u++) {
for(int i = 0, v, idx; i < min((int)init_g[u].size(), 2); i++) {
tie(v, idx) = init_g[u][i];
g[v + (idx == init_g[v][0].second) * n].push_back(u + i * n);
}
}
calc();
for(int i = 0; i < q; i++) res[i] += solve(len[i]);
p += n;
calc();
for(int i = 0; i < q; i++) res[i] += solve(len[i]);
for(int i = 0; i < q; i++) answer(res[i]);
}
