#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fr first
#define se second
struct Edge {
int idx, to;
Edge(int a = 0, int b = 0) : idx(a), to(b) {}
bool operator < (const Edge& a) const {
return (idx < a.idx);
}
};
const int MAXN = 150010;
const int INF = 0x3f3f3f3f;
const int MAXLOG = 30;
int n, m, p;
vector<Edge> adj[MAXN];
pii nxt[MAXN][2];
pii binl[30][MAXN][2];
int mi[MAXN];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P;
for (int i = 0; i < n; i++) {
mi[i] = INF;
}
for (int i = 0; i < m; i++) {
int a = R[i][0], b = R[i][1];
adj[a].push_back(Edge(i, b));
adj[b].push_back(Edge(i, a));
mi[a] = min(mi[a], i);
mi[b] = min(mi[b], i);
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
}
for (int i = 0; i < n; i++) {
// faz o do 0
bool f = 0;
if (mi[adj[i][0].to] == adj[i][0].idx) f = 1;
nxt[i][0] = make_pair(adj[i][0].to, f);
// faz o do 1
if (((int) adj[i].size()) == 1) {
nxt[i][1] = nxt[i][0];
} else {
f = 0;
if (mi[adj[i][1].to] == adj[i][1].idx) f = 1;
nxt[i][1] = make_pair(adj[i][1].to, f);
}
}
// calcular bin lift
for (int i = 0; i < n; i++) {
binl[0][i][0] = nxt[i][0];
binl[0][i][1] = nxt[i][1];
}
for (int k = 1; k < MAXLOG; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
pii a = binl[k - 1][i][j];
binl[k][i][j] = binl[k - 1][a.fr][a.se];
}
}
}
for (int q = 0; q < Q; q++) {
int k = G[q];
int ans = 0;
for (int i = 0; i < n; i++) {
pii curr = {i, 0};
for (int b = 0; b < MAXLOG; b++) {
if (k & (1 << b)) curr = binl[b][curr.fr][curr.se];
}
if (curr.fr == p) ans++;
}
answer(ans);
}
}
