#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
typedef long long ll;
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v[200010];
int p[30][300010];
int n;
int sol(int P,int k,int pos){
for(int i=0;i<30;i++){
if(k&(1<<i))pos=p[i][pos];
}
if(pos==P || pos==n+P)return 1;
return 0;
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[]){
n=N;
for(int i=0;i<M;i++){
if(v[R[i][0]].size()<2)v[R[i][0]].push_back(R[i][1]);
if(v[R[i][1]].size()<2)v[R[i][1]].push_back(R[i][0]);
}
for(int i=0;i<N;i++){
p[0][i]=v[i][0];
if(v[v[i][0]][0]==i)p[0][i]+=N;
}
for(int i=0;i<N;i++){
p[0][i+N]=v[i].back();
if(v[v[i].back()][0]==i)p[0][i+N]+=N;
}
for(int i=1;i<30;i++){
for(int j=0;j<2*N;j++){
p[i][j]=p[i-1][p[i-1][j]];
}
}
for(int i=0;i<Q;i++){
int tot=0;
for(int j=0;j<N;j++)tot+=sol(P,G[i],j);
answer(tot);
}
}
