#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using adj_list = vector<vector<int>>;
const int MAX = 1'000'000'000;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
adj_list g(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]);
}
int k = __lg(MAX);
vector<vector<pair<int, int>>> st0(N, vector<pair<int, int>>(k + 1));
vector<vector<pair<int, int>>> st1(N, vector<pair<int, int>>(k + 1));
for (int u = 0; u < N; ++u) {
st0[u][0] = {g[u].size() == 1 ? g[u][0] : g[u][1], u};
st1[u][0] = {g[u][0], u};
}
for (int i = 1; i <= k; ++i) {
for (int u = 0; u < N; ++u) {
int v, p;
tie(v, p) = st0[u][i - 1];
st0[u][i] = p == g[v][0] ? st0[v][i - 1] : st1[v][i - 1];
tie(v, p) = st1[u][i - 1];
st1[u][i] = p == g[v][0] ? st0[v][i - 1] : st1[v][i - 1];
}
}
vector<pair<int, int>> query(Q);
for (int q = 0; q < Q; ++q) {
query[q] = {G[q], q};
}
sort(query.begin(), query.end());
vector<int> ans(Q);
int t = 0;
vector<int> cnt0(N, 0);
vector<int> cnt1(N, 1);
set<int> alive;
for (int i = 0; i < N; ++i) {
alive.insert(i);
}
for (auto [q, id] : query) {
map<int, int> delta0, delta1;
int diff = q - t;
t = q;
for (int u : alive) {
{
int v = u, p = g[u][0];
for (int j = diff; j; j -= j & -j) {
int s = __builtin_ctz(j);
tie(v, p) = g[v][0] == p ? st0[v][s] : st1[v][s];
}
if (p == g[v][0])
delta0[v] += cnt0[u];
else
delta1[v] += cnt0[u];
delta0[u] -= cnt0[u];
}
{
int v = u, p = u;
for (int j = diff; j; j -= j & -j) {
int s = __builtin_ctz(j);
tie(v, p) = g[v][0] == p ? st0[v][s] : st1[v][s];
}
if (p == g[v][0])
delta0[v] += cnt1[u];
else
delta1[v] += cnt1[u];
delta1[u] -= cnt1[u];
}
}
for (auto [i, del] : delta0) {
cnt0[i] += del;
if (cnt0[i] == 0 && cnt1[i] == 0) alive.erase(i);
}
for (auto [i, del] : delta1) {
cnt1[i] += del;
if (cnt0[i] == 0 && cnt1[i] == 0) alive.erase(i);
}
ans[id] = cnt0[P] + cnt1[P];
}
for (int i : ans) {
answer(i);
}
}
