#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
/*
só interessam as duas arestas mais valiosas de um cara
ou vc ta em um ciclo ou vc escoa um ciclo
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 150000+10, MAXQ = 2e3+10, BIG = 1e9+1;
vector<pii> e[MAXN];
int ds[MAXN][2]; // distância até p
bool st[MAXN][2]; // o estado que pega p
bool dfs(int x, int l, int P){
bool cr = 0;
if (e[x].size() > 1 && l == e[x][0].second) cr=1;
if (ds[x][cr] != BIG) return cr;
ds[x][cr] = -1;
auto i = e[x][cr].first;
if (i == P){
ds[x][cr] = 1, st[x][cr] = (e[i].size()>1 && e[x][cr].second==e[i][0].second);
return cr;
}
bool is = dfs(i, e[x][cr].second, P);
if (ds[i][is] != -1){
ds[x][cr] = ds[i][is]+1;
st[x][cr] = st[i][is];
}
return cr;
}
void count_routes(int n, int m, int P, int R[][2], int q, int G[]){
for (int i=0;i<n;i++){
e[i].clear();
ds[i][0] = ds[i][1] = BIG;
}
for (int i=0;i<m;i++){
int a = R[i][0], b = R[i][1];
if (e[a].size()<2) e[a].emplace_back(b, i);
if (e[b].size()<2) e[b].emplace_back(a, i);
}
for (int i=0;i<n;i++){
if (ds[i][0] == BIG) dfs(i, -1, P);
}
dfs(P, e[P][0].second, P);
// for (int i=0;i<n;i++) cerr << ds[i][0] << ' ' << ds[i][1] << '\n';
for (int _=0;_<q;_++){
int sk = G[_], cr = 0;
for (int i=0;i<n;i++) if (ds[i][0] != -1 && ds[i][0]<=sk){
int k = sk;
long long d = ds[i][0];
if (d==k){
cr++;
// cerr << i << " can\n";
continue;
}
k-=d;
bool cst = st[i][0];
if (ds[P][cst] == -1) continue;
long long fcy = ds[P][cst];
k -= fcy;
if (k<=0){
cr+=(k==0);
continue;
}
bool nst = st[P][cst];
if (nst == cst){
cr += (k%fcy == 0);
continue;
}
long long scy = ds[P][nst];
bool tst = st[P][nst];
k -= scy;
if (k<=0){
cr += (k==0);
continue;
}
if (tst == nst){ // 1->2->2, ciclo simples
cr += (k%scy == 0);
continue;
}else{ // 1->2->1
// small = fcy, big = scy
long long rst = k%(fcy+scy);
if (rst==0 || rst==fcy) cr++;
continue;
}
}
answer(cr);
// cout << cr << '\n';
}
}
