#include <cstdint>
#include <vector>
#include <array>
using namespace std;
const size_t nil = SIZE_MAX;
void answer(int);
void count_routes(int _n, int _m, int _t, int E[][2], int _q, int K[])
{
const size_t n = _n, m = _m, target = _t, q = _q;
vector<array<size_t, 2>> to(n, {nil, nil});
for(size_t i = 0; i < m; i++)
{
size_t u = E[i][0], v = E[i][1];
if(to[u][0] == nil)
to[u][0] = v;
else if(to[u][1] == nil)
to[u][1] = u;
if(to[v][0] == nil)
to[v][0] = u;
else if(to[v][1] == nil)
to[v][1] = u;
}
vector<size_t> F(2*n, nil);
// vertex i+n is vertex after coming through best edge of vertex i
auto nfix = [&](size_t v, size_t u) {
return v + (to[v][0] == u ? n : 0);
};
for(size_t u = 0; u < n; u++)
{
F[u] = nfix(to[u][0], u);
F[u+n] = nfix(to[u][1] == nil ? to[u][0] : to[u][1], u);
}
for(size_t que = 0; que < q; que++)
{
size_t k = K[que];
int result = 0;
for(size_t u = 0; u < n; u++)
{
size_t v = u;
for(size_t i = 0; i < k; i++)
v = F[v];
if(v == target or v == target+n)
result++;
}
answer(result);
}
}
