#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000;
vector<vector<pair<int, int>>> conn(MAXN);
vector<vector<int>> adjT(MAXN);
const int pr = 150000;
int T[MAXN][2];
bool vis[MAXN][2];
bool on_cycle[2];
int C_Len = 2e9+5;
void dfs(int u, int cur, int idx, int start) {
if(u == start && vis[u][idx]) {
C_Len = cur;
on_cycle[idx] = true;
return;
}
if(vis[u][idx]) return;
vis[u][idx] = true;
T[u][idx] = cur;
for(int v : adjT[u]) {
dfs(v, cur + 1, idx, start);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
memset(T, -1, sizeof T);
for(int i = 0, a, b; i < M; ++i) {
a = R[i][0];
b = R[i][1];
conn[a].push_back({i, b});
conn[b].push_back({i, a});
}
for(int i = 0; i < N; ++i) sort(conn[i].begin(), conn[i].end());
for(int i = 0; i < N; ++i) {
int j, dest, idx;
bool usedBest;
j = conn[i][0].second;
usedBest = false;
if (conn[j][0].second == i) usedBest = true;
dest = usedBest ? j + pr : j;
adjT[dest].push_back(i);
idx = (conn[i].size() > 1 ? 1 : 0);
j = conn[i][idx].second;
usedBest = false;
if (conn[j][0].second == i) usedBest = true;
dest = usedBest ? j + pr : j;
adjT[dest].push_back(i + pr);
}
dfs(P, 0, 0, P);
dfs(P + pr, 0, 1, P + pr);
for(int k = 0; k < Q; ++k) {
int g = G[k];
int ans = 0;
for(int i = 0; i < N; ++i) {
bool ok = false;
for(int j = 0; j < 2; ++j) {
if(T[i][j] == -1 || g < T[i][j]) continue;
if(on_cycle[j]) {
ok |= ((g - T[i][j]) % C_Len) == 0;
} else {
ok |= (g - T[i][j]) == 0;
}
}
ans += ok;
}
answer(ans);
}
}
