#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],d1[maxn];
int n,m,r;
bool dbg=0;
void dcmp(){
vp0[r][0][0]=1;//find highest to go before crossing this edge
vp1[r][1][0]=1;
vp0[r][1][0]=1;
//vp1[r][0][0]=1;
for(int k=1;k<33;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];
//if(t.fi==0)debug(x)
x=t.fi;
y=t.se;
ans+=(1<<k);
//if(dbg)debug(x)
}
}
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(vp0[i][0][1])
//for(int i=0;i<=3;i++)debug(vp0[2][0][i])
//vector<pii> v0,v1;
for(int i=1;i<=n;i++){
d0[i]=bsta(i,0);
//debug(1)
d1[i]=bsta2(i,0);
//debug(2)
}
int oc=bsta2(p[r][1][0].fi,p[r][1][0].se)+1;
dbg=1;
//debug(1)
int zc=bsta(p[r][0][0].fi,p[r][0][0].se)+1;
//debug(1)
//debug(3)
//debugp(zc,oc)
pii q[Q];
for(int i=0;i<Q;i++){
q[i]={G[i],i};
}
sort(q,q+Q);
//for(int i=1;i<=n;i++)debug(d1[i])
sort(d0+1,d0+n+1);
sort(d1+1,d1+n+1);
map<int,int> m0,m1;
int ans[Q];
memset(ans,0,sizeof(ans));
int p1=0,p0=0;
for(auto [k,qi]:q){
while(p0<n&&d0[p0]<=k){
m0[d0[p0]%zc]++;
p0++;
}
while(p1<n&&d1[p1]<=k){
m1[d1[p1]%oc]++;
p1++;
}
//debugpl(m0)debugpl(m1)
ans[qi]=m0[k%zc]+m1[k%oc];
}
for(auto i:ans)answer(i);
}
