#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
vector<vector<int>> to(n);
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);
}
vector<int> nxt(2 * n, -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];
vector<vector<int>> jump(30, vector<int>(2 * n));
jump[0] = nxt;
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 = count(pos.begin(), pos.end(), p) +
count(pos.begin(), pos.end(), n + p);
answer(ans);
}
}
