#include <iostream>
#include <memory>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
void answer(int X);
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
// Build adjacency lists, but only keep up to 2 edges per node
vector<vector<int>> node_edges(N + 1);
for (int idx = 0; idx < M; ++idx) {
int i = R[idx][0];
int j = R[idx][1];
if (node_edges[i].size() < 2) {
node_edges[i].push_back(j);
}
if (node_edges[j].size() < 2) {
node_edges[j].push_back(i);
}
}
// Walk function: choose the neighbor that's not the one we came from
auto do_walk = [&](int walk, int prev_walk) {
if (node_edges[walk].empty()) {
// No neighbors, same
return walk;
}
int next_walk = node_edges[walk][0];
if (node_edges[walk].size() == 2 && next_walk == prev_walk) {
next_walk = node_edges[walk][1];
}
return next_walk;
};
map<pair<int, int>, pair<int, int>> state_to_cycle_start;
map<pair<int, int>, shared_ptr<deque<pair<int, int>> >> state_to_path;
map<pair<int, int>, shared_ptr<deque<pair<int, int>> >> state_to_cycle;
// Can we, starting from `node`, after g steps end up at node P?
auto can_from_node = [&](int node, int g) {
auto path = make_shared<deque<pair<int,int>>>();
set<pair<int,int>> visited;
int prev_walk = node;
int walk = do_walk(prev_walk, -1);
int next_walk = do_walk(walk, prev_walk); // uses default prev_walk = -1
while (g > 0) {
g--;
pair<int,int> state = make_pair(walk, next_walk);
if (state_to_path.find(state) != state_to_path.end()) { // cached
auto cached_path = state_to_path[state];
auto cycle_start = state_to_cycle_start[state];
// std::cout << "hit cache!" << std::endl;
auto it = std::find(cached_path->begin(), cached_path->end(), state);
auto it_cycle_start = std::find(cached_path->begin(), cached_path->end(), cycle_start);
if (it != cached_path->end()) {
size_t pos = std::distance(cached_path->begin(), it);
size_t pos_cycle = std::distance(cached_path->begin(), it_cycle_start);
int start_pos;
int g_rem;
if (pos >= pos_cycle) { // already in cycle
// std::cout << "already in cycle!" << std::endl;
start_pos = pos;
g_rem = g;
} else if (pos + g >= pos_cycle) { // can reach cycle
start_pos = pos_cycle;
g_rem = g - (pos_cycle - pos);
} else { // cannot reach cycle, pos + g < is in path
return (*cached_path)[pos + g].first == P; // no need for modulo
}
// get cycle
auto cycle = state_to_cycle[cycle_start];
// now cycle
auto c_size = cycle->size();
return (*cycle)[(start_pos + g_rem) % c_size].first == P;
} else {
// std::cout << "ERROR, not in cycle" << std::endl;
throw std::runtime_error("State not found in cached cycle");
}
}
if (visited.find(state) == visited.end()) {
visited.insert(state);
path->push_back(state);
int temp = walk;
walk = do_walk(walk, prev_walk);
if (temp == walk) {
return walk == P; // we are stuck at walk
}
prev_walk = temp;
next_walk = do_walk(walk, prev_walk);
} else {
// std::cout << "hit cycle!" << std::endl;
// std::cout << "g remaining " << g << std::endl;
// std::cout << "path: " << std::endl;
// for (int i = 0; i < path->size(); i++) {
// std::cout << (*path)[i].first << " " << (*path)[i].second << std::endl;
// }
// std::cout << "state: " << state.first << " " << state.second << std::endl;
auto cycle = make_shared<deque<pair<int, int>>>(*path);
while (cycle->front() != state) {
// std::cout << "popping " << cycle.front().first << " " << cycle.front().second << std::endl;
cycle->pop_front();
}
// now have a cycle
for (auto state_it = path->begin(); state_it != path->end(); ++state_it) {
// cache
state_to_path.insert({*state_it, path});
state_to_cycle_start.insert({*state_it, state});
state_to_cycle.insert({*state_it, cycle});
}
int c = cycle->size();
// std::cout << "cycle length " << c << std::endl;
return (*cycle)[g % c].first == P;
}
}
// std::cout << "found path:" << '\n';
// for (int i = 0; i < path->size(); i ++) {
// std::cout << (*path)[i].first << '\n';
// }
// std::cout << "--------" << '\n';
// After g steps, are we at P?
return path->back().first == P;
};
for (int i = 0; i < Q; i++) {
int g_val = G[i];
int count = 0;
// std::cout << "i " << i << std::endl;
for (int node = 0; node < N; ++node) {
// std::cout << "can from node: " << node << " " << g_val << std::endl;
bool can = can_from_node(node, g_val);
// std::cout << "can from node " << node << " " << g_val << ": " << can << std::endl;
if (can) {
count++;
}
// std::cout << "--------------------" << std::endl;
}
answer(count);
// std::cout << "----------------------------------------" << std::endl;
}
}
