#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
vector<vi> adj, F, adj2;
vi seen;
int C[3];
int N,P;
void join(int u, int v) {
if(seen[u] == 0) {
if(seen[v] == 0) adj[u].push_back(v+N);
else adj[u].push_back(v);
} else if(seen[u] == 1) {
if(seen[v] == 0) adj[u+N].push_back(v+N);
else adj[u+N].push_back(v);
}
}
void dfs(int u, int p, int idx) {
for(int i=0;i<adj2[u].size();i++) {
int v = adj2[u][i];
if(v==p) {
C[idx] = F[idx][u]+1;
} else if(F[idx][v] == -1){
F[idx][v] = F[idx][u]+1;
dfs(v, p, idx);
}
}
}
void precompute() {
F.assign(2, vi());
for(int i=0;i<2;i++) {
F[i].assign(2*N, -1);
C[i] = 0;
}
F[0][P] = 0;
dfs(P, P, 0);
F[1][P+N] = 0;
dfs(P+N, P+N, 1);
}
vi prev;
int solve(int k) {
int ans = 0;
for(int i=0;i<N;i++) {
bool ok = false;
for(int j=0;j<2;j++) {
if(F[j][i] == -1) continue;
else if(F[j][i] == k) {
//printf("MATCH: i=%d\n", i);
ok = true;
}
else if(C[j] && k>F[j][i] && (k-F[j][i])%C[j]==0) {
//printf("CYCLE: i=%d C[j]=%d\n", i, C[j]);
ok = true;
}
}
if(ok) ans++;
}
return ans;
}
void count_routes(int _N, int M, int _P, int R[][2], int Q, int G[]) {
P = _P;
N = _N;
adj.assign(2*N, vi());
adj2.assign(2*N, vi());
seen.assign(2*N, 0);
for(int i=0;i<M;i++) {
int u = R[i][0];
int v = R[i][1];
join(u,v);
join(v,u);
seen[u]++;
seen[v]++;
}
for(int i=0;i<N;i++) {
if(adj[i].size() == 0 && adj[i+N].size() == 1) adj[i].push_back(adj[i+N][0]);
if(adj[i].size() == 1 && adj[i+N].size() == 0) adj[i+N].push_back(adj[i][0]);
}
for(int u=0;u<2*N;u++) {
adj2[adj[u][0]].push_back(u);
}
//for(int i=0;i<N;i++) {
// if(adj2[i][0] >= N) printf("%d -> %d'\n", i, adj2[i][0]-N);
// else printf("%d -> %d\n", i, adj2[i][0]);
//}
//for(int i=N;i<2*N;i++) {
// if(adj2[i][0] >= N) printf("%d'-> %d'\n", i-N, adj2[i][0]-N);
// else printf("%d'-> %d\n", i-N, adj2[i][0]);
//}
precompute();
for(int q=0;q<Q;q++) {
answer(solve(G[q]));
}
}
