#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
using ii = pair<int, int>;
int to[300005], anc[35][300005];
bool out[300005];
vector<int> bits, in_nodes;
vector<ii> _adj[300005];
map<int, int> chc;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
for (int i = 0; i < M; i++) {
_adj[R[i][0]].eb(i, i << 1);
_adj[R[i][1]].eb(i, i << 1 | 1);
}
for (int i = 0; i < N; i++) sort(_adj[i].begin(), _adj[i].end());
for (int i = 0; i < M; i++) {
if (_adj[R[i][1]].size() == 1) to[i << 1] = (i << 1) ^ 1;
else to[i << 1] = ((_adj[R[i][1]][0].second >> 1) == i ? _adj[R[i][1]][1].second : _adj[R[i][1]][0].second);
if (_adj[R[i][0]].size() == 1) to[i << 1 | 1] = (i << 1 | 1) ^ 1;
else to[i << 1 | 1] = ((_adj[R[i][0]][0].second >> 1) == i ? _adj[R[i][0]][1].second : _adj[R[i][0]][0].second);
}
for (int i = 0; i < N; i++)
if (!_adj[i].empty()) in_nodes.pb(_adj[i][0].second);
for (int i = 0; i < M; i++) {
if (R[i][0] == P) out[i << 1 | 1] = 1;
if (R[i][1] == P) out[i << 1] = 1;
}
for (int k = 0; k < 30; k++) {
for (int i = 0; i < (M << 1); i++)
if (k == 0) anc[k][i] = to[i];
else anc[k][i] = anc[k - 1][anc[k - 1][i]];
}
for (int i = 0, ans, curr; i < Q; i++) {
G[i]--;
if (chc.find(G[i]) != chc.end()) {
answer(chc[G[i]]);
continue;
}
ans = 0;
bits.clear();
for (int j = 0; G[i]; j++, G[i] >>= 1)
if (G[i] & 1) bits.pb(j);
for (int j : in_nodes) {
curr = j;
for (int k : bits)
curr = anc[k][curr];
if (out[curr]) ans++;
}
chc[G[i]] = ans;
answer(ans);
}
}
