#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
vector<pii> to;
vector<int> arr, arr2, tmp1, tmp2;
void calc(int n, int b){
tmp2.resize(n); tmp1.resize(n);
iota(all(tmp1), 0); arr2 = arr;
do{
//for(auto i: tmp1)cout << i << " "; cout << endl;
//for(auto i: arr2)cout << i << " "; cout << endl;
if(b&1)
for(int i = 0; i < n; i++)tmp1[i] = arr2[tmp1[i]];
for(int i = 0; i < n; i++)tmp2[i] = arr2[arr2[i]];
arr2 = tmp2;
}while(b>>=1);
}
vector<int> ans1, ans2, gone;
void dfs(int i, int P, vector<int>& ans){
if(arr[i] == P){
ans[i] = 1;
return;
}
if(!gone[arr[i]]){
gone[arr[i]] = true;
dfs(arr[i], P, ans);
}
if(ans[arr[i]] != INT_MAX)ans[i] = ans[arr[i]]+1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
to.resize(N, {-1, -1}); arr.resize(2*N);
for(int i = 0; i < M; i++){
if(to[R[i][0]].ff == -1)to[R[i][0]].ff = R[i][1];
else if(to[R[i][0]].ss == -1)to[R[i][0]].ss = R[i][1];
if(to[R[i][1]].ff == -1)to[R[i][1]].ff = R[i][0];
else if(to[R[i][1]].ss == -1)to[R[i][1]].ss = R[i][0];
}
for(int i = 0; i < N; i++){
if(to[i].ss == -1)to[i].ss = to[i].ff;
arr[2*i] = 2*to[i].ff + (to[to[i].ff].ff == i);
arr[2*i+1] = 2*to[i].ss + (to[to[i].ss].ff == i);
}
//for(auto i: to)cout << i.ff << " " << i.ss << " "; cout << endl;
//for(auto i: arr)cout << i << " "; cout << endl;
ans1.resize(2*N, INT_MAX); ans2.resize(2*N, INT_MAX); gone.resize(2*N, 0);
for(int i = 0; i < 2*N; i++) if(!gone[i])dfs(i, 2*P, ans1);
fill(all(gone), 0);
for(int i = 0; i < 2*N; i++) if(!gone[i])dfs(i, 2*P+1, ans2);
//for(auto i: ans1)cout << i << " "; cout << endl;
//for(auto i: ans2)cout << i << " "; cout << endl;
int d1 = 0, d2 = 0; swap(ans1[2*P], d1); swap(ans2[2*P+1], d2);
for(int j=0; j<Q; j++){
//for(auto i: tmp1)cout << i << " "; cout << endl;
int ans = 0;
for(int i = 0; i < N; i++)
if(ans1[2*i] != INT_MAX && ans1[2*i] >= G[j] && (ans1[2*i] - G[j])%d1 == 0 || ans2[2*i] != INT_MAX && ans2[2*i] >= G[j] && (ans2[2*i] - G[j])%d2 == 0)ans++;
answer(ans);
}
}
