#include "garden.h"
#include "gardenlib.h"
#include"bits/stdc++.h"
using namespace std;
int nxt[150001][2];
int dp[150001][2][32];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
for (int i = 0 ; i < M ; i++) {
auto [u, v] = R[i];
u++, v++;
if (!nxt[u][0] and !nxt[v][0]) {
nxt[u][0] = -v;
nxt[v][0] = -u;
}
if (!nxt[u][0]) nxt[u][0] = v;
if (!nxt[v][0]) nxt[v][0] = u;
if (abs(nxt[u][0]) != v and nxt[u][1] == 0) {
if (abs(nxt[v][0]) == u) nxt[u][1] = -v;
else nxt[u][1] = v;
}
if (abs(nxt[v][0]) != u and nxt[v][1] == 0) {
if (abs(nxt[u][0]) == v) nxt[v][1] = -u;
else nxt[v][1] = u;
}
}
for (int i = 1 ; i <= N ; i++) {
if (nxt[i][1] == 0) nxt[i][1] = nxt[i][0];
}
// for (int i = 1 ; i <= N ; i++) {
// cout << i << ": " << nxt[i][0] << " " << nxt[i][1] << endl;
// }
for (int j = 0 ; j < 32 ; j++) {
for (int i = 1 ; i <= N ; i++) {
for (int k = 0 ; k < 2 ; k++) {
if (j == 0) {
dp[i][k][j] = nxt[i][k];
} else {
int x = dp[i][k][j-1];
int u = abs(x);
int v = x < 0;
dp[i][k][j] = dp[u][v][j-1];
}
}
}
}
for (int q = 0 ; q < Q ; q++) {
int k = G[q];
int ans = 0;
for (int i = 1 ; i <= N ; i++) {
int u = i, v = 0;
for (int j = 31 ; j >= 0 ; j--) {
if (k & (1 << j)) {
int x = dp[u][v][j];
u = abs(x);
v = x < 0;
}
}
// cerr << q << ": " << i << " " << u << endl;
if (u == P + 1) {
ans++;
}
}
answer(ans);
}
}
