#include <iostream>
#include <vector>
#include <algorithm>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define all(x) x.begin(), x.end()
#define _2 second
#define pb push_back
typedef pair<int, int> P;
int N, M, T, Q;
vector<P> G[150000];
int best[150000];
int F[30][150000*2];
inline int fg(P p) {
int x = p._2, e = p._1;
if (best[x] == e) return x+N;
else return x;
}
inline int go(int x, int s) {
for (int k=29; k>=0; k--) if ((s>>k)&1) x = F[k][x];
return x;
}
void count_routes(int n, int m, int p, int edges[][2], int q, int g[]) {
N = n, M = m, T = p, Q = q;
rep(i, N) G[i].clear();
rep(i, M) {
G[edges[i][0]].pb(P(i, edges[i][1]));
G[edges[i][1]].pb(P(i, edges[i][0]));
}
rep(i, N) {
sort(all(G[i]));
best[i] = G[i][0]._1;
}
rep(i, N) {
F[0][i] = fg(G[i][0]);
F[0][i+N] = fg((G[i].size()>=2)? G[i][1] : G[i][0]);
}
rep(k, 29) {
rep(i, N) F[k+1][i] = F[k][F[k][i]];
}
rep(i, Q) {
int k = g[i];
int ctr = 0;
rep(x, N) {
int v = go(x, k);
if (v == T || v == T+N) ctr++;
}
answer(ctr);
}
}
