#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int MAXN = (int)(150000);
const int INF = (int)(2e9);
vector<int> revadj[2*MAXN];
int first[MAXN];
int second[MAXN];
int to[2*MAXN];
bool seen[2*MAXN];
int dist[2*MAXN][2];
int oppose(int a, int r[2]) {
if (r[0] == a) {
return r[1];
}
return r[0];
}
int checkLoop(int start) {
memset(seen, 0, sizeof(seen));
int ori = start;
int cnt = 1;
seen[start] = true;
while (!seen[to[start]]) {
cnt++;
start = to[start];
seen[start] = true;
}
start = to[start];
if (ori != start) {
return INF;
}
else {
return cnt;
}
}
void mdist(int start) {
int id = start&1;
for (int i = 0; i < 2*MAXN; i++){
dist[i][id] = INF;
}
deque<int> deq;
deq.push_back(start);
dist[start][id] = 0;
while (deq.size()) {
int n = deq.front();
deq.pop_front();
for (int e : revadj[n]) {
if (dist[e][id] > dist[n][id] + 1) {
dist[e][id] = dist[n][id]+1;
deq.push_back(e);
}
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
fill(all(first), -1);
fill(all(second), -1);
for (int i = 0; i < M; i++) {
for (int j = 0; j < 2; j++) {
if (first[R[i][j]] == -1) {
first[R[i][j]] = i;
}
else if (second[R[i][j]] == -1) {
second[R[i][j]] = i;
}
}
}
for (int i = 0; i < N; i++) {
int fv = oppose(i, R[first[i]]);
if (first[fv] == first[i]) {
to[2*i] = 2*fv+1;
}
else {
to[2*i] = 2*fv;
}
if (second[i] != -1) {
int sv = oppose(i, R[second[i]]);
if (first[sv] == second[i]) {
to[2*i+1] = 2*sv+1;
}
else {
to[2*i+1] = 2*sv;
}
}
else {
to[2*i+1] = to[2*i];
}
revadj[to[2*i]].push_back(2*i);
revadj[to[2*i+1]].push_back(2*i+1);
}
int lp[2];
lp[0] = checkLoop(2*P);
lp[1] = checkLoop(2*P+1);
mdist(2*P);
mdist(2*P+1);
for (int iter = 0; iter < Q; iter++) {
int k = G[iter];
int cnt = 0;
for (int i =0; i < 2*N; i+=2) {
bool good = false;
if (dist[i][0] <= k && (k-dist[i][0])%lp[0] == 0) {
good = true;
}
if (dist[i][1] <= k && (k-dist[i][1])%lp[1] == 0) {
good = true;
}
cnt += good;
}
answer(cnt);
}
}
