#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mxN = 150000+5;
pii lift[3*mxN][31];
int rev[3*mxN];
vector<vector<int>> adj;
void count_routes(int N, int M, int p, int r[][2], int q, int g[]) {
int n = N, m = M;
vector<vector<int>> adj(n);
map<pii, int> mp;
map<int, pii> rev;
int id=0;
for (int i=0; i<m; i++) {
int a, b;
a = r[i][0];
b = r[i][1];
if (adj[a].size()<2) {
adj[a].push_back(b);
mp[{b, a}] = id;
rev[id] = {b, a};
id++;
}
if (adj[b].size()<2) {
adj[b].push_back(a);
mp[{a, b}] = id;
rev[id] = {a, b};
id++;
}
}
for (int i=0; i<id; i++) {
int a = rev[i].first;
int b = rev[i].second;
//Estado (a, b) llegue a a desde b
if (adj[a].size()==1) {
lift[i][0].first = mp[{adj[a][0], a}];
lift[i][0].second = i;
}
else {
lift[i][0].first = (b==adj[a][0] ? mp[{adj[a][1], a}] : mp[{adj[a][0], a}]);
lift[i][0].second = i;
}
}
for (int j=1; j<31; j++) {
for (int i=0; i<id; i++) {
int a = lift[i][j].first;
int b = lift[i][j].second;
lift[i][j].first = lift[lift[i][j-1].first][j-1].first;
lift[i][j].second = lift[lift[i][j-1].first][j-1].second;
}
}
//cout << rev[aux].first << " " << rev[aux].second << endl;
for (int i=0; i<q; i++) {
int k = g[i];
k--;
int ans=0;
for (int j=0; j<n; j++) {
int nxt = adj[j][0];
int node = mp[{nxt, j}];
for (int b=0; b<31; b++) {
if (k&(1<<b)) {
node = lift[node][b].first;
//cout << node << " " << u << " " << v << endl;
}
}
int a = rev[node].first;
int b = rev[node].second;
//cout << node << " " << a << " " << b << endl;
if (a == p) ans++;
}
answer(ans);
}
}
