#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int deg[N], Mn[N], F[N], D[N], n, Res[N];
bool v[N];
vector < int > E[N];
void DFS(int a, int d)
{
int i;
D[a] = d;
for (i = 0; i < (int)E[a].size(); i++){
if (D[E[a][i]] == -1)DFS(E[a][i], d + 1);
}
}
int QQ, DD[N];
struct Query{
int a, num;
bool operator<(const Query &p)const{
return a < p.a;
}
}w[N];
int S[N];
void Do(int a){
int i, x, c = 0, cnt = 0, pv;
for (i = 0; i < 2 * n; i++){
D[i] = -1;
v[i] = false;
S[i] = 0;
}
DFS(a, 0);
for (i = 0; i < n; i++){
if (D[i] != -1){
DD[cnt++] = D[i];
}
}
sort(DD, DD + cnt);
x = a;
while (!v[x]){
c++;
v[x] = true;
x = F[x];
}
if (x != a){
c = 1000000009;
}
pv = 0;
for (i = 0; i < QQ; i++){
while (pv < cnt && DD[pv] <= w[i].a){
S[DD[pv] % c]++;
pv++;
}
if (w[i].a%c > 2 * n)continue;
Res[w[i].num] += S[w[i].a%c];
}
}
void Add(int a, int b, int i){
if (Mn[a] == i){
if (Mn[b] != i || deg[b] == 1)F[a] = b;
else F[a] = b + n;
}
else if (F[a + n] == -1){
if (Mn[b] != i || deg[b] == 1)F[a + n] = b;
else F[a + n] = b + n;
}
}
void count_routes(int N2, int M, int P, int R[][2], int Q, int G[])
{
int i, a, b;
n = N2;
QQ = Q;
for (i = 0; i < Q; i++){
w[i].a = G[i];
w[i].num = i;
}
sort(w, w + Q);
for (i = 0; i < 2 * N2; i++)F[i] = -1;
for (i = 0; i < M; i++){
a = R[i][0], b = R[i][1];
deg[a]++, deg[b]++;
if (!Mn[a])Mn[a] = i + 1;
if (!Mn[b])Mn[b] = i + 1;
}
for (i = 0; i < M; i++){
a = R[i][0], b = R[i][1];
Add(a, b, i+1);
Add(b, a, i+1);
}
for (i = 0; i < N2; i++){
E[F[i]].push_back(i);
if (deg[i]>1)E[F[i + N2]].push_back(i + N2);
}
Do(P);
if (deg[P] != 1)Do(P + N2);
for (i = 0; i < Q; i++)answer(Res[i]);
}
