#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
// Step 1: Compute the most beautiful and second most beautiful edges for each node
vector<int> most_beautiful(N, -1);
vector<int> second_most_beautiful(N, -1);
// Process edges to find most and second most beautiful connections
for (int i = 0; i < M; i++) {
int a = R[i][0], b = R[i][1];
// For node a
if (most_beautiful[a] == -1) {
most_beautiful[a] = b;
} else if (second_most_beautiful[a] == -1) {
second_most_beautiful[a] = b;
}
// For node b
if (most_beautiful[b] == -1) {
most_beautiful[b] = a;
} else if (second_most_beautiful[b] == -1) {
second_most_beautiful[b] = a;
}
}
// For nodes with only one edge, use the same edge as both most and second most beautiful
for (int i = 0; i < N; i++) {
if (second_most_beautiful[i] == -1) {
second_most_beautiful[i] = most_beautiful[i];
}
}
// Step 2: Build the successor graph (functional graph where each node has exactly one outgoing edge)
// We have 2*N nodes: nodes 0 to N-1 represent original nodes, nodes N to 2N-1 represent alternative states
vector<int> next(2 * N, -1);
for (int i = 0; i < N; i++) {
int f = most_beautiful[i];
int s = second_most_beautiful[i];
// Determine successors based on how we arrive at each node
next[i] = (most_beautiful[f] == i) ? f + N : f;
next[i + N] = (most_beautiful[s] == i) ? s + N : s;
}
// Step 3: Find cycle lengths using Floyd's tortoise and hare algorithm
// Find cycle for node P
int cycle_len1 = INT_MAX;
int tortoise = P, hare = next[P];
// Detect cycle
while (tortoise != hare && hare != -1) {
tortoise = next[tortoise];
hare = next[hare];
if (hare != -1) hare = next[hare];
}
if (hare != -1) { // Cycle exists
// Find cycle length
tortoise = P;
int steps = 0;
// Find entry point to cycle
while (tortoise != hare) {
tortoise = next[tortoise];
hare = next[hare];
steps++;
}
// Measure cycle length
int cycle_start = tortoise;
cycle_len1 = 1;
tortoise = next[tortoise];
while (tortoise != cycle_start) {
cycle_len1++;
tortoise = next[tortoise];
}
}
// Find cycle for node P+N (alternative state)
int cycle_len2 = INT_MAX;
tortoise = P + N;
hare = next[P + N];
// Detect cycle
while (tortoise != hare && hare != -1) {
tortoise = next[tortoise];
hare = next[hare];
if (hare != -1) hare = next[hare];
}
if (hare != -1) { // Cycle exists
// Find cycle length
tortoise = P + N;
int steps = 0;
// Find entry point to cycle
while (tortoise != hare) {
tortoise = next[tortoise];
hare = next[hare];
steps++;
}
// Measure cycle length
int cycle_start = tortoise;
cycle_len2 = 1;
tortoise = next[tortoise];
while (tortoise != cycle_start) {
cycle_len2++;
tortoise = next[tortoise];
}
}
// Step 4: Compute distances using BFS (more memory-efficient than recursive DFS)
vector<int> dist1(2 * N, -1);
vector<int> dist2(2 * N, -1);
// Build reverse graph for BFS
vector<vector<int>> rev_graph(2 * N);
for (int i = 0; i < 2 * N; i++) {
if (next[i] != -1) {
rev_graph[next[i]].push_back(i);
}
}
// BFS from node P
queue<int> q1;
q1.push(P);
dist1[P] = 0;
while (!q1.empty()) {
int v = q1.front();
q1.pop();
for (int u : rev_graph[v]) {
if (dist1[u] == -1) {
dist1[u] = dist1[v] + 1;
q1.push(u);
}
}
}
// BFS from node P+N
queue<int> q2;
q2.push(P + N);
dist2[P + N] = 0;
while (!q2.empty()) {
int v = q2.front();
q2.pop();
for (int u : rev_graph[v]) {
if (dist2[u] == -1) {
dist2[u] = dist2[v] + 1;
q2.push(u);
}
}
}
// Step 5: Process queries
for (int i = 0; i < Q; i++) {
int K = G[i];
int count = 0;
for (int j = 0; j < N; j++) {
// Check if we can reach node j from P in exactly K steps
if (dist1[j] != -1 && dist1[j] <= K && (dist1[j] == K || (cycle_len1 != INT_MAX && (K - dist1[j]) % cycle_len1 == 0))) {
count++;
}
// Check if we can reach node j from P+N in exactly K steps
if (dist2[j] != -1 && dist2[j] <= K && (dist2[j] == K || (cycle_len2 != INT_MAX && (K - dist2[j]) % cycle_len2 == 0))) {
count++;
}
}
answer(count);
}
}
