#include "garden.h"
#include "gardenlib.h"
#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)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++: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 nxt[30][300005];
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)) nxt[0][x]=al[v[x]][0];
else nxt[0][x]=al[v[x]][1];
}
//rep(x,0,m*2) cout<<nxt[0][x]<<endl;
rep(layer,0,29){
rep(x,0,m*2){
nxt[layer+1][x]=nxt[layer][nxt[layer][x]];
}
}
rep(x,0,q){
int ans=0;
g[x]--;
rep(y,0,n){
int curr=al[y][0];
rep(layer,0,30) if (g[x]&(1<<layer)) curr=nxt[layer][curr];
if (v[curr]==k) ans++;
}
answer(ans);
}
}
