#include "garden.h"
#include "gardenlib.h"
//Segment Tree is a State of Mind
#pragma GCC optimize("O2,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugp(x,y) cerr<<#x<<' '<<#y<<" is "<<x<<' '<<y<<endl;
#define debugl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p<<" ";cerr<<endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<" , ";cerr<<endl;
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define rdint(x,y) rnd()%(y-x+1)+x
const int inf=4e18+5;
const int mod=1e9+7;
const int mod2=998244353;
const int mod3=1e9+9;
const int maxn=2e5+5;
pii p[maxn][2][33];
bool vp0[maxn][2][33];
bool vp1[maxn][2][33];
int d0[maxn][2];
int n,m,r;
void dcmp(){
vp0[r][0][0]=1;//find highest to go before crossing this edge
vp1[r][1][0]=1;
for(int k=1;k<32;k++){
for(int i=1;i<=n;i++){
p[i][0][k]=p[p[i][0][k-1].fi][p[i][0][k-1].se][k-1];
p[i][1][k]=p[p[i][1][k-1].fi][p[i][1][k-1].se][k-1];
vp0[i][0][k]=vp0[i][0][k-1]||vp0[p[i][0][k-1].fi][p[i][0][k-1].se][k-1];
vp1[i][0][k]=vp1[i][0][k-1]||vp1[p[i][0][k-1].fi][p[i][0][k-1].se][k-1];
vp0[i][1][k]=vp0[i][1][k-1]||vp0[p[i][1][k-1].fi][p[i][1][k-1].se][k-1];
vp1[i][1][k]=vp1[i][1][k-1]||vp1[p[i][1][k-1].fi][p[i][1][k-1].se][k-1];
}
}
}
int bsta(int x,int y){
int ans=0;
for(int k=32;k>=0;k--){
if(vp0[x][y][k]==0){
pii t=p[x][y][k];
x=t.fi;
y=t.se;
ans+=(1<<k);
}
}
return ans;
}
int bsta2(int x,int y){
int ans=0;
for(int k=32;k>=0;k--){
if(vp1[x][y][k]==0){
pii t=p[x][y][k];
x=t.fi;
y=t.se;
ans+=(1<<k);
}
}
return ans;
}
pii kpar(int x,int y,int k){
for(int i=0;i<33;i++){
if((1LL<<i)&k){
pii t=p[x][y][i];
x=t.fi;
y=t.se;
//debug(x)
}
}
return {x,y};
}
void count_routes(signed N, signed M, signed P, signed R[][2], signed Q, signed G[]){
n=N,m=M,r=P+1;
for(int i=0;i<m;i++){
R[i][0]++,R[i][1]++;
//debug(R[i][0])
bool b=0;
if(p[R[i][0]][0][0].fi==0){
b=1;
if(p[R[i][1]][0][0].fi==0)p[R[i][0]][0][0]={R[i][1],1};//best edge
else p[R[i][0]][0][0]={R[i][1],0};
}else if(p[R[i][0]][1][0].fi==0){
if(p[R[i][1]][0][0].fi==0)p[R[i][0]][1][0]={R[i][1],1};
else p[R[i][0]][1][0]={R[i][1],0};
}
if(p[R[i][1]][0][0].fi==0){
p[R[i][1]][0][0].fi=R[i][0];
if(b)p[R[i][1]][0][0].se=1;
else p[R[i][1]][0][0].se=0;
}else if(p[R[i][1]][1][0].fi==0){
p[R[i][1]][1][0].fi=R[i][0];
if(b)p[R[i][1]][1][0].se=1;
else p[R[i][1]][1][0].se=0;
}
}
for(int i=1;i<=n;i++){
if(p[i][1][0].fi==0)p[i][1][0]=p[i][0][0];
}
dcmp();
//for(int i=1;i<=n;i++)debug(p[i][0][0].fi)
for(int q=0;q<Q;q++){
int ans=0;
int k=G[q];
//debug(k)
for(int i=1;i<=n;i++){
int kp=kpar(i,0,k).fi;
//debug(kp)
if(kp==r)ans++;
}
answer(ans);
}
}
