#pragma GCC optimize("O2,unroll-loops")
#include"garden.h"
#include"gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
int up[30][300005],cnt[300005];
void count_routes(int n,int m,int P,int R[][2],int Q,int G[]){
memset(up,-1,sizeof up);
for(int i=0;i<m;i++){
int f=R[i][0],t=R[i][1];
if(cnt[f]<2)up[0][(f<<1)+cnt[f]]=(t<<1)+(cnt[t]==0);
if(cnt[t]<2)up[0][(t<<1)+cnt[t]]=(f<<1)+(cnt[f]==0);
cnt[f]++,cnt[t]++;
}
for(int i=0;i<(n<<1);i++)if(up[0][i]<0)up[0][i]=up[0][i^1];
for(int i=1;i<30;i++)
for(int j=0;j<(n<<1);j++)
up[i][j]=up[i-1][up[i-1][j]];
for(int I=0;I<Q;I++){
int ans=0;
for(int i=0;i<(n<<1);i+=2)cnt[i]=i;
for(int i=0;i<30;i++)
if((G[I]>>i)&1)
for(int j=0;j<(n<<1);j+=2)
cnt[j]=up[i][cnt[j]];
for(int i=0;i<(n<<1);i+=2)ans+=cnt[i]==(P<<1)||cnt[i]==(P<<1|1);
answer(ans);
}
}
