#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
vector<pii> to;
vector<int> arr, arr2, tmp1, tmp2;
void calc(int n, int b){
tmp2.resize(n); tmp1.resize(n);
iota(all(tmp1), 0); arr2 = arr;
do{
//for(auto i: tmp1)cout << i << " "; cout << endl;
//for(auto i: arr2)cout << i << " "; cout << endl;
if(b&1)
for(int i = 0; i < n; i++)tmp1[i] = arr2[tmp1[i]];
for(int i = 0; i < n; i++)tmp2[i] = arr2[arr2[i]];
arr2 = tmp2;
}while(b>>=1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
to.resize(N, {-1, -1}); arr.resize(2*N);
for(int i = 0; i < M; i++){
if(to[R[i][0]].ff == -1)to[R[i][0]].ff = R[i][1];
else if(to[R[i][0]].ss == -1)to[R[i][0]].ss = R[i][1];
if(to[R[i][1]].ff == -1)to[R[i][1]].ff = R[i][0];
else if(to[R[i][1]].ss == -1)to[R[i][1]].ss = R[i][0];
}
for(int i = 0; i < N; i++){
if(to[i].ss == -1)to[i].ss = to[i].ff;
arr[2*i] = 2*to[i].ff + (to[to[i].ff].ff == i);
arr[2*i+1] = 2*to[i].ss + (to[to[i].ss].ff == i);
}
//for(auto i: to)cout << i.ff << " " << i.ss << " "; cout << endl;
//for(auto i: arr)cout << i << " "; cout << endl;
for(int i=0; i<Q; i++){
calc(2*N, G[i]);
//for(auto i: tmp1)cout << i << " "; cout << endl;
int ans = 0;
for(int i = 0; i < N; i++)
if(tmp1[2*i]/2 == P)ans++;
answer(ans);
}
}
