#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150000;
const int MAXLOG = 30;
const int MAXM = 150000;
pair<int,int> f[MAXLOG+1][MAXN][2];
vector<vector<int>> adj;
int n, m;
pair<int,int> pai(pair<int,int> u) {
int e = 0;
if (u.second == 1 and (int)adj[u.first].size() > 1) { // já veio de grande
e = 1;
}
int v = adj[u.first][e];
bool is_v_biggest = false;
if (adj[v][0] == u.first) is_v_biggest = true;
return {v, is_v_biggest};
};
pair<int,int> move(pair<int,int> v, int step) {
for (int b=MAXLOG; b>=0; b--) {
if ((1 << b) > step) continue;
step -= (1 << b);
v = f[b][v.first][v.second];
}
return v;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N; m = M;
adj = vector<vector<int>>(n);
for (int e=0; e<m; e++) {
int u = R[e][0], v = R[e][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i=0; i<n; i++) {
for (int state=0; state<=1; state++) {
f[0][i][state] = pai({i, state});
}
}
for (int b=1; b<=MAXLOG; b++) {
for (int i=0; i<n; i++) {
for (int state=0; state<=1; state++) {
pair<int,int> mid = f[b-1][i][state];
f[b][i][state] = f[b-1][mid.first][mid.second];
}
}
}
for(int g=0; g<Q; g++) {
int ans = 0;
for (int i=0; i<n; i++) {
pair<int,int> dest = move({i, 0}, G[g]);
if (dest.first == P) {
ans++;
}
}
answer(ans);
}
}
