#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150005;
int to[MAXN][2];
int dp[31][MAXN][2];
int pos[MAXN];
void count_routes(int n, int m, int p, int R[][2], int q, int G[]) {
vector<int> g[MAXN];
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]);
}
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end());
for (int j = 0; j < g[i].size(); j++) {
int x = i, y = g[i][j];
pos[x] = j;
}
}
for (int i = 0; i < n; i++) {
if (g[i].size() == 1) {
to[i][0] = g[i][0];
to[i][1] = g[i][0];
} else {
to[i][0] = g[i][0];
to[i][1] = g[i][1];
}
}
for (int i = 0; i < n; i++) {
for (int b = 0; b < 2; b++) {
int x = to[i][b];
int idx = (g[x][0] == i ? 0 : 1);
dp[0][i][b] = (to[x][idx] == p);
}
}
for (int k = 1; k <= 30; k++) {
for (int i = 0; i < n; i++) {
for (int b = 0; b < 2; b++) {
int x = to[i][b];
int back = (g[x][0] == i ? 0 : 1);
int y = to[x][back];
dp[k][i][b] = dp[k - 1][x][back];
to[i][b] = y;
}
}
}
for (int i = 0; i < q; i++) {
int k = G[i];
long long res = 0;
for (int v = 0; v < n; v++) {
for (int b = 0; b < (g[v].size()); b++) {
int x = v, y = to[v][b];
bool ok = true;
for (int bit = 0; bit <= 30; bit++) {
if ((k >> bit) & 1) {
if (dp[bit][x][(g[x][0] == y ? 0 : 1)]) {
int nx = to[x][(g[x][0] == y ? 0 : 1)];
y = x;
x = nx;
} else {
ok = false;
break;
}
}
}
if (ok && x == p) res++;
}
}
answer(res);
}
}
