#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector< pii > g[150001];
int dp[150001][2][31];
int last[150001][2][31];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for (int i = 0; i < M; ++i) {
g[R[i][0]].push_back(make_pair(R[i][1], i));
g[R[i][1]].push_back(make_pair(R[i][0], i));
}
memset(dp, -1, sizeof dp);
for (int i = 0 ; i < N ; i++) {
if (g[i].size()) {
dp[i][0][0] = dp[i][1][0] = g[i][0].first;
last[i][0][0] = last[i][1][0] = g[i][0].second;
}
if (g[i].size() > 1) {
dp[i][1][0] = g[i][1].first;
last[i][1][0] = g[i][1].second;
}
}
for (int k = 1 ; k <= 30; k++)
for (int i = 0 ; i < N ; i++) {
for (int it = 0 ; it < 2 ; it++) {
if (dp[i][it][k - 1] != -1) {
int vv = dp[i][it][k - 1];
int uu = last[i][it][k - 1];
dp[i][it][k] = dp[vv][(g[vv][0].second == uu)][k - 1];
last[i][it][k] = last[vv][(g[vv][0].second == uu)][k-1];
}
}
}
for(int i = 0 ; i < Q ; i++){
int cnt = 0;
for(int j = 0 ; j < N ; j++){
int go = j;
int ll = -1;
int tmp = G[i];
for(int k = 30 ; k >= 0;k--){
if((1 << k) <= tmp){
tmp -= (1 << k);
int nw =dp[go][ll == g[go][0].second][k];
ll = last[go][ll == g[go][0].second][k];
go = nw;
}
}
if(go == P)
cnt++;
}
answer(cnt);
}
}
