#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;
constexpr int maxn = 1.5e5, maxg = 1e9, maxq = 2e3 + 5, bit = 32 - __builtin_clz(maxg), siz = 1 << bit;
int goal;
basic_string <int> adj[maxn];
// Jumping (1 << i) steps from each node, taking the best way or the second
// store whether we need to use the best or second best route
arr jump[bit][maxn][2] = { 0 };
void count_routes(int n, int m, int P, int R[][2], int Q, int G[])
{
goal = P;
for (int i = 0; i < m; i++)
{
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
// Making the only way a second way if needed
for (int i = 0; i < n; i++)
{
if (adj[i].size() == 1) adj[i].push_back(adj[i][0]);
}
for (int i = 0; i < n; i++)
{
for (int y = 0; y < 2; y++)
{
jump[0][i][y] = {adj[i][y], adj[adj[i][y]][0] == i};
}
}
for (int b = 1; b < bit; b++)
{
for (int i = 0; i < n; i++)
{
for (int y = 0; y < 2; y++)
{
jump[b][i][y] = jump[b - 1][jump[b - 1][i][y][0]][jump[b - 1][i][y][1]];
}
}
}
vector <arr> queries(Q);
for (int i = 0; i < Q; i++) queries[i] = { G[i], i };
sort(queries.begin(), queries.end());
arr pos;
map<arr, int> pos_count, next_count;
for (int i = 0; i < n; i++) pos_count[{i, 0}] = 1;
int last = 0;
int diff;
vector <int> output(Q);
for (int y = 0; y < Q; y++) // 2e3
{
diff = queries[y][0] - last;
for (auto pa : pos_count)
{
pos = pa.first;
for (int j = 0; j < bit; j++) // 30
{
if (diff & (1 << j)) pos = jump[j][pos[0]][pos[1]];
}
next_count[pos] += pa.second;
}
output[queries[y][1]] = next_count[{P, 0}] + next_count[{P, 1}];
last = queries[y][0];
pos_count.swap(next_count);
next_count.clear();
}
for (int i: output) answer(i);
}
