#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <tuple>
#include <cassert>
using namespace std;
const int N = 3e5 + 1, INF = 1e9+1;
int n, p, q, res[N], cycle_idx[N], d[N];
vector<int> g[N], gt[N], cycle, cnt[N];
vector<pair<int, int>> init_g[N];
bool oncycle[N];
int mark[N];
stack<int> st;
void dfs_cycle(int u, int par) {
// cout << u << ' ' << par << endl;
mark[u] = 1;
st.push(u);
for(int v: g[u]) if(v != par) {
if(!mark[v]) dfs_cycle(v, u);
else if(mark[v] == 1) {
// cout << v << endl;
stack<int> tmp;
while(st.top() != v) {
cycle.push_back(st.top());
oncycle[st.top()] = true;
tmp.push(st.top());
st.pop();
}
cycle.push_back(v);
oncycle[v] = true;
reverse(cycle.begin(), cycle.end());
while(!tmp.empty()) st.push(tmp.top()), tmp.pop();
}
}
st.pop();
mark[u] = 2;
}
void dfs_tree(int u, int par) {
if(u < n) {
if (cnt[cycle_idx[u]].size() < d[u]+1)
cnt[cycle_idx[u]].resize(d[u] + 1);
++cnt[cycle_idx[u]][d[u]];
}
for(int v: gt[u]) if(v != par && !oncycle[v]) {
d[v] = d[u] + 1;
cycle_idx[v] = cycle_idx[u];
dfs_tree(v, u);
}
}
void calc() {
fill(mark, mark+2*n, 0);
fill(oncycle, oncycle+2*n, 0);
fill(cycle_idx, cycle_idx+2*n, -1);
cycle.clear();
dfs_cycle(p, -1);
// for(int i = 0; i < cycle.size(); i++) cout << cycle[i] << ' ';
// cout << endl;
for(int i = 0; i < cycle.size(); i++) {
cycle_idx[cycle[i]] = i;
dfs_tree(cycle[i], cycle[i]);
}
}
int solve(int len) {
if(d[p]) {
return (len + d[p] < cnt[cycle_idx[p]].size()
? cnt[cycle_idx[p]][len + d[p]]
: 0);
}
// assume !d[p]
int ret = 0;
for(int i = 0; i < n; i++) if(cycle_idx[i] != -1) { // only consider (i, 0)
int sz = cycle.size();
int cycle_dist = (cycle_idx[p] + sz - cycle_idx[i]) % sz;
// cout << i << ' ' << cycle_dist << ' ' << (len - d[i] - cycle_dist) % sz << endl;
ret += d[i] + cycle_dist <= len && !((len - d[i] - cycle_dist) % sz);
}
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++) {
init_g[_e[i][0]].emplace_back(_e[i][1], i);
init_g[_e[i][1]].emplace_back(_e[i][0], i);
}
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[u + i * n].push_back(v + (init_g[v].size() > 1 && idx == init_g[v][0].second) * n);
// cout << u + i * n << ' ' << v + (init_g[v].size() > 1 && idx == init_g[v][0].second) * n << endl;
gt[v + (init_g[v].size() > 1 && 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]);
// cout << res[0] << endl;
p += n;
calc();
for(int i = 0; i < q; i++) res[i] += solve(len[i]);
// cout << res[0] << endl;
for(int i = 0; i < q; i++) answer(res[i]);
}
