#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int MAXN = 2e5 + 10;
vector<pair<int, int>> adj[MAXN];
pair<int, int> dp_1[30][MAXN], dp_2[30][MAXN];
void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
for(int i=0; i<n; i++) adj[i].clear();
for(int i=0; i<m; i++){
adj[r[i][0]].push_back({i, r[i][1]});
adj[r[i][1]].push_back({i, r[i][0]});
}
for(int i=0; i<n; i++){
sort(adj[i].begin(), adj[i].end());
dp_1[0][i] = {adj[i][0].second, adj[i][0].first};
// vertice, aresta
if(adj[i].size() > 1){
dp_2[0][i] = {adj[i][1].second, adj[i][1].first};
} else dp_2[0][i] = dp_1[0][i];
}
for(int k=1; k<30; k++){
for(int i=0; i<n; i++){
auto [nxt_1, e_1] = dp_1[k - 1][i];
if(e_1 == adj[nxt_1][0].first){
dp_1[k][i] = dp_2[k - 1][nxt_1];
} else dp_1[k][i] = dp_1[k - 1][nxt_1];
auto [nxt_2, e_2] = dp_2[k - 1][i];
if(e_2 == adj[nxt_2][0].first){
dp_2[k][i] = dp_2[k - 1][nxt_2];
} else dp_2[k][i] = dp_1[k - 1][nxt_2];
}
}
for(int i=0; i<q; i++){
int cnt = 0;
for(int j=0; j<n; j++){
int cur = j;
for(int k=0; k<30; k++){
if(g[i] & (1 << k)){
cur = dp_1[k][cur].first;
}
}
if(cur == p) cnt ++;
}
answer(cnt);
}
}
