#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
igrid roads;
int createNode (int node, bool cMax) {
return 2 * node + (cMax ? 1 : 0);
}
idata functional_graph;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
roads.resize(N);
for (int i = M - 1; i >= 0; i --) {
roads[R[i][0]].push_back(R[i][1]);
roads[R[i][1]].push_back(R[i][0]);
}
functional_graph.resize(2 * N);
for (int i = 0; i < N; i ++) {
idata &l_roads = roads[i];
int nmax = l_roads[l_roads.size() - 1];
int nmix = l_roads[max(0, (int) l_roads.size() - 2)];
functional_graph[2 * i] = 2 * nmax + (roads[nmax][roads[nmax].size() - 1] == i ? 1 : 0);
functional_graph[2 * i + 1] = 2 * nmix + (roads[nmix][roads[nmix].size() - 1] == i ? 1 : 0);
}
for (int i = 0; i < Q; i ++) {
int duration = G[i];
int count = 0;
for (int j = 0; j < N; j ++) {
int x = 2 * j;
for (int t = 0; t < duration; t ++)
x = functional_graph[x];
if (x == 2 * P || x == 2 * P + 1) count ++;
}
answer(count);
}
}
