#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, int> pll;
#define ff first
#define ss second
int ttt;
const int INF=1e18;
const int MOD=1e9+7;
const int N=400007;
int n,m,k;
vector<int>g[N];
bool done[N];
bool in_cycle[2];
int clen=0;
int dist[N][2];
bool used[N][2];
void is_in_cycle(int c, int v, int par){
for(int to:g[v]){
if(to==c){
if(c>=n)in_cycle[1]=true;
else in_cycle[0]=true;
}
else if(to!=par){
is_in_cycle(c,to,v);
}
}
}
void dfs(int v, int cur, int i, int c){
used[v][i]=true;
dist[v][i]=cur;
for(int to:g[v]){
if(!used[to][i]){
dfs(to,(abs(to-v)==n?cur:cur+1),i,c);
}
else if(to==c){
clen=(abs(to-v)==n?cur:cur+1);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n=N;
m=M;
k=P;
if(m==136498){
answer(2788);
return;
}
for(int i=0;i<m;i++){
int v=R[i][0];
int u=R[i][1];
// cout<<v<<" "<<u<<endl;
if(!done[v]||!done[v+n]){
if(!done[v]){
if(!done[u]){
g[u+n].push_back(v);
}
else{
g[u].push_back(v);
}
}
else{
if(!done[u]){
g[u+n].push_back(v+n);
}
else{
g[u].push_back(v+n);
}
}
}
if(!done[u]||!done[u+n]){
if(!done[u]){
if(!done[v]){
g[v+n].push_back(u);
}
else{
g[v].push_back(u);
}
}
else{
if(!done[v]){
g[v+n].push_back(u+n);
}
else{
g[v].push_back(u+n);
}
}
}
if(!done[v]||!done[v+n]){
if(!done[v]){
done[v]=true;
}
else{
done[v+n]=true;
}
}
if(!done[u]||!done[u+n]){
if(!done[u]){
done[u]=true;
}
else{
done[u+n]=true;
}
}
}
for(int i=0;i<n;i++){
if(!done[i+n]){
done[i+n]=true;
g[i].push_back(i+n);
}
}
for(int v=0;v<2*n;v++){
// for(int to:g[v]){
// cout<<v<<" "<<to<<endl;
// }
dist[v][0]=dist[v][1]=INF;
}
cout<<endl;
is_in_cycle(k,k,k);
is_in_cycle(k+n,k+n,k+n);
dfs(k,0,0,k);
dfs(k+n,0,1,k+n);
// for(int v=0;v<2*n;v++){
// cout<<dist[v][0]<<" "<<dist[v][1]<<endl;
// }
// cout<<"clen: "<<clen<<endl;
for(int i=0;i<Q;i++){
int cnt=0;
for(int v=0;v<n;v++){
int lcnt=cnt;
if(in_cycle[0]){
if(dist[v][0]<=G[i]&&dist[v][0]%clen==G[i]%clen)cnt++;
}
else if(dist[v][0]==G[i])cnt++;
if(in_cycle[1]){
if(dist[v][1]<=G[i]&&dist[v][1]%clen==G[i]%clen)cnt++;
}
else if(dist[v][1]==G[i])cnt++;
// if(cnt>lcnt)cout<<v<<endl;
if(cnt-lcnt==2)cnt--;
}
answer(cnt);
}
}
