#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdint>
#include <algorithm>
#include <cmath>
using namespace std;
using StateKey = uint64_t;
inline StateKey pack_state(int walk, int prev) {
return (uint64_t(walk) << 32) | uint32_t(prev);
}
void answer(int X);
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
// 1) Build adjacency lists (up to 2 edges per node)
vector<vector<int>> node_edges(N);
node_edges.reserve(N);
for (int idx = 0; idx < M; ++idx) {
int u = R[idx][0];
int v = R[idx][1];
if (node_edges[u].size() < 2) node_edges[u].push_back(v);
if (node_edges[v].size() < 2) node_edges[v].push_back(u);
}
// 2) Enumerate all possible states (walk, prev)
vector<pair<int,int>> states;
states.reserve(2 * N);
for (int u = 0; u < N; ++u) {
if (node_edges[u].empty()) {
// isolated or dead end: self-loop state
states.emplace_back(u, u);
} else {
for (int v : node_edges[u]) {
states.emplace_back(u, v);
}
}
}
int S = states.size();
// 3) Map each state to a compact ID
unordered_map<StateKey, int> state_id;
state_id.reserve(S);
for (int i = 0; i < S; ++i) {
state_id[pack_state(states[i].first, states[i].second)] = i;
}
// 4) Precompute successor and node_of_state arrays
vector<int> succ(S), node_of_state(S);
for (int i = 0; i < S; ++i) {
int walk = states[i].first;
int prev = states[i].second;
// do_walk:
int next = walk;
if (!node_edges[walk].empty()) {
next = node_edges[walk][0];
if (node_edges[walk].size() == 2 && next == prev)
next = node_edges[walk][1];
}
StateKey key = pack_state(next, walk);
succ[i] = state_id[key];
node_of_state[i] = walk;
}
// 5) Precompute binary-lifting table for fast jumps
int maxG = 0;
for (int i = 0; i < Q; ++i) maxG = max(maxG, G[i]);
int LOG = (maxG > 0 ? floor(log2(maxG)) + 1 : 1);
vector<vector<int>> lift(LOG, vector<int>(S));
// lift[0] = direct successor
lift[0] = succ;
for (int k = 1; k < LOG; ++k) {
for (int i = 0; i < S; ++i) {
lift[k][i] = lift[k-1][ lift[k-1][i] ];
}
}
// 6) Precompute initial state IDs for each starting node
vector<int> init_state(N);
for (int u = 0; u < N; ++u) {
if (node_edges[u].empty()) {
init_state[u] = state_id[pack_state(u, u)];
} else {
int first = node_edges[u][0];
init_state[u] = state_id[pack_state(first, u)];
}
}
// 7) Answer each query in O(N * LOG)
for (int qi = 0; qi < Q; ++qi) {
int g = G[qi];
int cnt = 0;
for (int u = 0; u < N; ++u) {
int s = init_state[u];
int steps = g;
for (int k = 0; k < LOG; ++k) {
if (steps & (1 << k)) {
s = lift[k][s];
}
}
if (node_of_state[s] == P) {
++cnt;
}
}
answer(cnt);
}
}
