#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7, INF=1e9+7;
int nxt[LIM], odl[LIM], cnt[LIM], ile[LIM][2], ans[LIM][2], cykl[2], n;
vector<int>V[LIM];
void sortuj() {
int ma=0, ilei=0;
rep(i, n) {
if(odl[i]==INF) ++ilei;
else ma=max(ma, odl[i]);
}
rep(i, n) if(odl[i]<INF) ++cnt[odl[i]];
int l=0;
for(int i=0; cnt[ma]; ++i) {
while(!cnt[l]) ++l;
odl[i]=l;
--cnt[l];
}
for(int i=n-1; ilei; --i, --ilei) odl[i]=INF;
}
void solve(int x, int r) {
cykl[r]=INF;
rep(i, 2*n) odl[i]=INF;
odl[x]=0;
queue<int>q;
q.push(x);
while(!q.empty()) {
int p=q.front(); q.pop();
for(auto i : V[p]) if(odl[i]>odl[p]+1) {
odl[i]=odl[p]+1;
q.push(i);
}
for(auto i : V[p]) if(i==x) cykl[r]=odl[p]+1;
}
sortuj();
int l=0;
rep(i, LIM) {
int s=l;
while(s<n && odl[s]==i) {
++ans[i][r];
++s;
}
if(cykl[r]<INF) {
ans[i][r]+=ile[i%cykl[r]][r];
}
while(l<n && odl[l]==i) {
++ile[i%cykl[r]][r];
++l;
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n=N;
rep(i, 2*n) nxt[i]=-1;
rep(i, M) {
int p1=R[i][1], p2=R[i][0];
if(nxt[R[i][1]]==-1) p1+=n;
if(nxt[R[i][0]]==-1) p2+=n;
if(nxt[R[i][0]]==-1) nxt[R[i][0]]=p1;
else if(nxt[R[i][0]+n]==-1) nxt[R[i][0]+n]=p1;
if(nxt[R[i][1]]==-1) nxt[R[i][1]]=p2;
else if(nxt[R[i][1]+n]==-1) nxt[R[i][1]+n]=p2;
}
rep(i, n) if(nxt[i]!=-1 && nxt[n+i]==-1) nxt[n+i]=nxt[i];
rep(i, 2*n) if(nxt[i]!=-1) V[nxt[i]].pb(i);
solve(P, 0);
solve(P+n, 1);
rep(i, Q) {
if(G[i]<LIM) answer(ans[G[i]][0]+ans[G[i]][1]);
else {
int x=0;
if(cykl[0]<INF) x+=ile[G[i]%cykl[0]][0];
if(cykl[1]<INF) x+=ile[G[i]%cykl[1]][1];
answer(x);
}
}
}
