#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int inf = 1e9;
const int MxN = 1e5 + 10;
const int MxL = 32;
int n, m, p, q, ans[MxN], g[MxN];
pii up[MxN][MxL][2];
vector<pii> adj[MxN];
int cnt = -1;
pii dfs(int u, int l, int op) {
if (l == 0) {
return up[u][l][op] = pii(adj[u][op].second, u);
}
if (up[u][l][op] != pii(-1, -1)) return up[u][l][op];
pii cur = pii(u, -1);
cur = dfs(cur.first, l - 1, op);
int new_op = 0;
if (cur.second == adj[cur.first][0].second) new_op = 1;
cur = dfs(cur.first, l - 1, new_op);
return up[u][l][op] = cur;
}
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 < M; i++) {
int u = R[i][0];
int v = R[i][1];
adj[u].push_back({i, v});
adj[v].push_back({i, u});
}
q = Q;
for (int i = 0; i < Q; i++) {
g[i] = G[i];
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
if (adj[i].size() == 1) adj[i].push_back({-1, adj[i][0].second});
adj[i].resize(2);
}
for (int j = 0; j < MxL; j++) {
for (int i = 0; i < n; i++) {
up[i][j][0] = up[i][j][1] = pii(-1, -1);
dfs(i, j, 0); dfs(i, j, 1);
}
}
for (int i = 0; i < q; i++) {
int ans = 0;
for (int j = 0; j < n; j++) {
pii cur = pii(j, -1);
int op = 0;
for (int k = 0; k < MxL; k++) {
if (g[i] & (1 << k)) {
cur = up[cur.first][k][op];
if (cur.second == adj[cur.first][0].second) op = 1;
else op = 0;
}
}
if (cur.first == p) ans++;
}
answer(ans);
}
}
