#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
#define mem(a , b) memset(a, b ,sizeof(a))
const ll N = 2e5 + 5;
const ll INF = 1e9 + 3;
vector < ll > v[N];
ii nxt(ll node, ll t){
if(v[node].size() == 1 && t > 0) t = 0;
return {v[node][t] , ((node == v[v[node][t]][0] && v[v[node][t]].size() > 1) ? 1 : 0)};
}
ll vis[N][2];
ll dp[N][2][2], P;
ll go(ll node, ll t, ll tar){
if(make_pair(node, t) == make_pair(P, tar)){
return dp[node][t][tar] = 0;
}
if(dp[node][t][tar] != -1){
return dp[node][t][tar];
}
vis[node][t] = 1;
auto [n1, t1] = nxt(node, t);
if(vis[n1][t1] == 1){
vis[node][t] = 2;
return dp[node][t][tar] = INF;
}
dp[node][t][tar] = min(INF, go(n1, t1, tar) + 1);
vis[node][t] = 2;
return dp[node][t][tar];
}
void count_routes(int n, int m, int _P, int R[][2], int Q, int G[]){
P = _P;
for(ll i = 0; i < m; i++){
v[R[i][0]].pb(R[i][1]);
v[R[i][1]].pb(R[i][0]);
}
ll cycle[2] = {0, 0};
mem(vis, 0);
ii cur = {P, 0};
while(true){
vis[cur.ff][cur.ss] = 1;
//cout << cur.ff << ' ' << cur.ss << '\n';
ii NXT = nxt(cur.ff, cur.ss);
cycle[0]++;
if(NXT == make_pair(P, 0)){
break;
}
if(vis[NXT.ff][NXT.ss]){
cycle[0] = INF;
break;
}
cur = NXT;
}
if(v[P].size() == 1){
cycle[1] = INF;
}else{
mem(vis, 0);
cur = {P, 1};
while(true){
vis[cur.ff][cur.ss] = 1;
ii NXT = nxt(cur.ff, cur.ss);
cycle[1]++;
if(NXT == make_pair(P, 1)){
break;
}
if(vis[NXT.ff][NXT.ss]){
cycle[1] = INF;
break;
}
cur = NXT;
}
}
//cout << cycle[0] << ' ' << cycle[1] << '\n';
mem(dp, -1);
for(ll tar = 0; tar < 2; tar++){
mem(vis, 0);
for(ll i = 0; i < n; i++){
for(ll j = 0; j < 1; j++){
go(i, j, tar);
}
}
}
for(ll j = 0; j < Q; j++){
ll ans = 0;
for(ll tar = 0; tar < 2; tar++){
for(ll i = 0; i < n; i++){
if(dp[i][0][tar] <= G[j] && (G[j] - dp[i][0][tar]) % cycle[tar] == 0){
ans++;
}
}
}
answer(ans);
}
return;
}
