#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
const ll INF = 1e9;
const ll MAXN = 2 * 150001;
ll V, E, dest;
vector<ll> graph[MAXN];
ll lenMove[MAXN];
ll adj[MAXN];
vector<ll> revAdj[MAXN];
ll jump[MAXN][33];
ll distGo (ll node, ll len) {
for (ll i = 0; i < 33; i++) {
if (len & (1ll << i)) {
node = jump[node][i];
}
}
return node;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
V = N, E = M, dest = P;
for (ll i = 0; i < Q; i++) {
lenMove[i] = G[i];
}
for (ll i = 0; i < E; i++) {
graph[R[i][0]].push_back(R[i][1]);
graph[R[i][1]].push_back(R[i][0]);
}
for (ll i = 0; i < V; i++) {
if (graph[graph[i][0]][0] == i) {
adj[i] = graph[i][0] + V;
revAdj[adj[i]].push_back(i);
}
else {
adj[i] = graph[i][0];
revAdj[adj[i]].push_back(i);
}
}
for (ll i = 0; i < V; i++) {
if (graph[i].size() > 1 && graph[graph[i][1]][0] == i) {
adj[i + V] = graph[i][1] + V;
revAdj[adj[i + V]].push_back(i + V);
}
else if (graph[i].size() == 1 && graph[graph[i][0]][0] == i) {
adj[i + V] = graph[i][0] + V;
revAdj[adj[i + V]].push_back(i + V);
}
else {
adj[i + V] = graph[i][1];
revAdj[adj[i + V]].push_back(i + V);
}
}
for (ll i = 0; i < 2*V; i++) {
jump[i][0] = adj[i];
}
for (ll i = 1; i < 33; i++) {
for (ll node = 0; node < 2*N; node++) {
jump[node][i] = jump[jump[node][i-1]][i-1];
}
}
ll endOn;
ll ans;
for (ll q = 0; q < Q; q++) {
ans = 0;
for (ll node = 0; node < V; node++) {
endOn = distGo(node, lenMove[q]);
if (endOn == dest || endOn == dest+V) {
ans++;
}
}
answer(ans);
}
}
