#include "garden.h"
#include "gardenlib.h"
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define rep(x,start,end) for(auto x=start;x!=end;x++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int n,m,k,q;
vector<int> al[150005];
int v[300005];
int par[32][300005];
int nxt[8][16][300005];
int node[150005];
void count_routes(int N, int M, int P, int R[][2], int Q, int g[]){
n=N,m=M,k=P,q=Q;
rep(x,0,m){
al[R[x][0]].push_back(x*2);
al[R[x][1]].push_back(x*2+1);
v[x*2]=R[x][1];
v[x*2+1]=R[x][0];
}
rep(x,0,m*2){
if (sz(al[v[x]])==1 || (al[v[x]][0]>>1)!=(x>>1)) par[0][x]=al[v[x]][0];
else par[0][x]=al[v[x]][1];
}
//rep(x,0,m*2) cout<<nxt[0][x]<<endl;
rep(layer,0,31){
rep(x,0,m*2){
par[layer+1][x]=par[layer][par[layer][x]];
}
}
rep(layer,0,8){
rep(bm,0,16){
rep(x,0,m*2){
int curr=x;
rep(bit,0,4) if (bm&(1<<bit)){
curr=par[layer*4+bit][curr];
}
nxt[layer][bm][x]=curr;
}
}
}
rep(x,0,q){
int ans=0;
g[x]--;
rep(y,0,n) node[y]=al[y][0];
rep(layer,0,8){
int *arr=nxt[layer][g[x]&15];
rep(y,0,n) node[y]=arr[node[y]];
g[x]>>=4;
}
rep(y,0,n) if (v[node[y]]==k) ans++;
answer(ans);
}
}
