#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 0x3fffffff;
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
void answer(int x);
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
vector g(N, array{pii{INF, -1}, pii{INF, -1}});
// 各頂点から最も美しい 2 つの辺を持つ
for(int i = 0; i < M; i++){
auto [a, b] = R[i];
if(chmin(g[a][1], {i, b}) && g[a][1] < g[a][0]) swap(g[a][0], g[a][1]);
if(chmin(g[b][1], {i, a}) && g[b][1] < g[b][0]) swap(g[b][0], g[b][1]);
}
for(auto& [e1, e2] : g) if(e2.first == INF) e2 = e1;
vector next(30, vector<int>(N * 2));
// ダブリング
for(int i = 0; i < N; i++){
{
const auto [a, b] = g[i][0];
if(a != INF) next[0][i * 2] = b * 2 + (a == g[b][0].first);
}
{
const auto [a, b] = g[i][1];
if(a != INF) next[0][i * 2 + 1] = b * 2 + (a == g[b][0].first);
}
}
for(int i = 0; i < 29; i++) for(int j = 0; j < N * 2; j++) next[i + 1][j] = next[i][next[i][j]];
for(int i = 0; i < Q; i++){
const int K = G[i];
int ans = 0;
for(int i = 0; i < N; i++){
int at = i * 2;
for(int i = 0; K >> i; i++) if(K >> i & 1) at = next[i][at];
ans += at / 2 == P;
}
answer(ans);
}
}
