#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pb push_back
using ll = long long;
int n, m, p, q;
vector<vector<pair<int, int>>> min_edge;
vector<vector<pair<int, int>>> graph;
vector<vector<int>> edges;
vector<int> act;
vector<int> D1, D2, L, C;
int get_dest(pair<int, int> edge) {
return edges[edge.first][edge.second];
}
pair<int, int> get_next(pair<int, int> edge) {
int v = get_dest(edge);
if(edge.first != min_edge[v][0].first) {
return min_edge[v][0];
}
else {
return min_edge[v][1];
}
}
int get_id(pair<int, int> edge) {
return edge.first + (m * edge.second);
}
constexpr int UNVISITED = (-2e9);
constexpr int UNREACHABLE = (2e9);
int timer = 0;
int sgn(int val) {
if(val < 0) return (-1);
if(val == 0) return 0;
return 1;
}
int lo = 1e9;
void dfs_cyc(pair<int, int> edge) {
int id = get_id(edge);
act[id] = ++timer;
auto nxt = get_next(edge);
int nxt_id = get_id(nxt);
if(act[nxt_id]) {
C[id] = C[nxt_id] = (act[id] - act[nxt_id]) + 1;
lo = act[nxt_id];
}
else {
if(C[nxt_id] == UNVISITED) {
dfs_cyc(nxt);
}
}
if(act[id] >= lo) {
L[id] = 1;
}
if(lo == act[id]) {
lo = 1e9;
}
C[id] = C[nxt_id];
act[id] = 0;
}
void dfs1(pair<int, int> edge) {
int v = get_dest(edge);
int id = get_id(edge);
D1[id] = UNREACHABLE;
if(v == p && edge.first == min_edge[v][0].first) {
if(L[id] || L[get_id(get_next(edge))]) {
D1[id] = 1;
}
else {
D1[id] = (-1);
}
return;
}
auto nxt = get_next(edge);
int new_id = get_id(nxt);
if(D1[new_id] == UNVISITED) {
dfs1(nxt);
}
if(D1[new_id] == UNREACHABLE) {
D1[id] = UNREACHABLE;
}
else {
D1[id] = D1[new_id] + sgn(D1[new_id]);
}
}
void dfs2(pair<int, int> edge) {
int v = get_dest(edge);
int id = get_id(edge);
D2[id] = UNREACHABLE;
if(v == p && edge.first != min_edge[v][0].first) {
if(L[id] || L[get_id(get_next(edge))]) {
D2[id] = 1;
}
else {
D2[id] = (-1);
}
return;
}
auto nxt = get_next(edge);
int new_id = get_id(nxt);
if(D2[new_id] == UNVISITED) {
dfs2(nxt);
}
if(D2[new_id] == UNREACHABLE) {
D2[id] = UNREACHABLE;
}
else {
D2[id] = D2[new_id] + sgn(D2[new_id]);
}
}
map<int, map<int, vector<int>>> c_to_rem_cyclic_cnt;
map<int, int> non_cyclic;
void count_routes(int N, int M, int P, int _edges[][2], int Q, int _G[]) {
n = N, m = M, p = P, q = Q;
edges.resize(m, vector<int>(2));
loop(i, 0, m-1) {
loop(j, 0, 1) {
edges[i][j] = _edges[i][j];
}
}
graph.resize(n);
loop(i, 0, m-1) {
int a = edges[i][0];
int b = edges[i][1];
graph[a].pb({ i, 1 });
graph[b].pb({ i, 0 });
}
min_edge.resize(n, vector<pair<int, int>>(2, { 1e9, (-1) }));
D1.resize(2 * m, UNVISITED);
D2.resize(2 * m, UNVISITED);
C.resize(2 * m, UNVISITED);
act.resize(2 * m, 0);
L.resize(2 * m, 0);
loop(i, 0, n-1) {
for(pair<int, int> state : graph[i]) {
if(state < min_edge[i][0]) {
min_edge[i][1] = min_edge[i][0];
min_edge[i][0] = state;
}
else if(state < min_edge[i][1]) {
min_edge[i][1] = state;
}
}
if(sz(graph[i]) == 1) {
min_edge[i][1] = min_edge[i][0];
}
}
loop(i, 0, n-1) {
dfs_cyc(min_edge[i][0]);
}
loop(i, 0, n-1) {
auto e = min_edge[i][0];
if(D1[get_id(e)] == UNVISITED) {
dfs1(e);
}
if(D2[get_id(e)] == UNVISITED) {
dfs2(e);
}
assert(D2[get_id(e)] != UNVISITED);
}
loop(i, 0, n-1) {
int id = get_id(min_edge[i][0]);
for(int d : { D1[id], D2[id] }) {
if(d == UNREACHABLE) continue;
if(d < 0) {
++non_cyclic[(-d)];
}
else {
c_to_rem_cyclic_cnt[C[id]][d % C[id]].pb(d);
}
}
}
for(auto& [ _, ma ] : c_to_rem_cyclic_cnt) {
for(auto& [ __, ve ] : ma) {
sort(all(ve));
}
}
loop(qi, 0, q-1) {
int k = _G[qi];
if(k == 0) {
answer(1);
continue;
}
int res = 0;
for(auto const& [ c, ma ] : c_to_rem_cyclic_cnt) {
auto it = ma.find(k % c);
if(it != ma.end()) {
int cnt = (upper_bound(all(it->second), k) - it->second.begin());
res += cnt;
}
}
{
auto it = non_cyclic.find(k);
if(it != non_cyclic.end()) {
res += it->second;
}
}
answer(res);
}
}
