#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
const int N = 150000;
vector<int> to[N];
int nxt[2 * N];
int jump[30][2 * N];
void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
for (int i = 0; i < m; ++i) {
int a = r[i][0], b = r[i][1];
if ((int)to[a].size() < 2) to[a].emplace_back(b);
if ((int)to[b].size() < 2) to[b].emplace_back(a);
}
for (int i = 0; i < 2 * n; ++i) nxt[i] = -1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2 && j < (int)to[i].size(); ++j) {
int x = to[i][j];
int node = (to[x][0] == i) * n + x;
nxt[j * n + i] = node;
}
}
for (int i = n; i < 2 * n; ++i) if (nxt[i] == -1) nxt[i] = nxt[i - n];
for (int i = 0; i < 2 * n; ++i) jump[0][i] = nxt[i];
for (int i = 1; i < 30; ++i) {
for (int j = 0; j < 2 * n; ++j) {
jump[i][j] = jump[i - 1][jump[i - 1][j]];
}
}
vector<int> pos(n);
for (int it = 0; it < q; ++it) {
int k = qrs[it];
iota(pos.begin(), pos.end(), 0);
for (int bit = 0; k; ++bit) {
if (!(k & (1 << bit))) continue;
k ^= 1 << bit;
for (int i = 0; i < n; ++i) {
pos[i] = jump[bit][pos[i]];
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += pos[i] == p || pos[i] == n + p;
}
answer(ans);
}
}
