#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 300069;
int up[N], vis[N], n, nxt[N], deg[N], dep1[N], sz[N], dep2[N];
vector<int> t[N], rn[N];
void dfs(int v) {
vis[v] = 1;
if (t[t[v][0]][0] == v && (int)t[t[v][0]].size() > 1) {
nxt[v] = n + t[v][0], deg[n + t[v][0]]++;
rn[n + t[v][0]].push_back(v);
}
else {
nxt[v] = t[v][0], deg[t[v][0]]++;
rn[t[v][0]].push_back(v);
}
if (t[v].size() > 1) {
if (t[t[v][1]][0] == v && (int)t[t[v][1]].size() > 1) {
nxt[n + v] = n + t[v][1], deg[n + t[v][1]]++;
rn[n + t[v][1]].push_back(n + v);
}
else {
nxt[n + v] = t[v][1], deg[t[v][1]]++;
rn[t[v][1]].push_back(n + v);
}
}
for (auto u : t[v]) {
if (!vis[u])
dfs(u);
}
}
void count_routes(int n1, int m, int p, int r[][2], int q, int k[])
{
++p;
n = n1;
for (int i = 0;i < m;i++) {
r[i][0]++, r[i][1]++;
t[r[i][0]].push_back(r[i][1]);
t[r[i][1]].push_back(r[i][0]);
}
for (int i = 1;i <= n;i++) {
if (!vis[i])
dfs(i);
}
for (int i = 1;i <= 2 * n;i++) {
dep1[i] = dep2[i] = 1e9;
}
queue<int> que;
que.push(p);
dep1[p] = dep2[n + p] = 0;
//cepamo reverse
while (!que.empty()) {
auto v = que.front();
que.pop();
for (auto r : rn[v]) {
if (dep1[r] <= dep1[v] + 1)
continue;
dep1[r] = dep1[v] + 1;
que.push(r);
}
}
que.push(n + p);
while (!que.empty()) {
auto v = que.front();
que.pop();
for (auto r : rn[v]) {
if (dep2[r] <= dep2[v] + 1)
continue;
dep2[r] = dep2[v] + 1;
que.push(r);
}
}
for (int i = 1;i <= 2 * n;i++) {
if (deg[i] == 0)
que.push(i);
}
fill(vis, vis + 2 * n + 1, 0);
while (!que.empty()) {
auto v = que.front();
vis[v] = 1;
que.pop();
int r = nxt[v];
if (r != 0) {
deg[r]--;
if (deg[r] == 0)
que.push(r);
}
}
for (int i = 1;i <= 2 * n;i++) {
if (!vis[i]) {
int t = i, s = 0;
vector<int> o;
while (t > 0 && !vis[t]) {
vis[t] = 1;
up[t] = t;
o.push_back(t);
++s;
t = nxt[t];
}
for (auto u : o)
sz[u] = s;
}
}
for (int i = 0;i < q;i++) {
int ans = 0;
for (int j = 1;j <= n;j++) {
//up[v] = v // u ciklusu je
int o = 0;
if (up[p] == p) {
if (dep1[j] != 1e9 && dep1[j] <= k[i]) {
int x = k[i] - dep1[j];
o |= (x % sz[p] == 0);
}
}
else if (up[p] != p)
o |= (dep1[j] == k[i]);
int p1 = n + p;
if (up[p1] == p1) {
if (dep2[j] != 1e9 && dep2[j] <= k[i]) {
int x = k[i] - dep2[j];
o |= (x % sz[p1] == 0);
}
}
else if (up[p1] != p1)
o |= (dep2[j] == k[i]);
ans += o;
}
answer(ans);
}
}
