#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define _2 second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef pair<int, int> P;
int N, M, T, Q;
vector<P> G[150000];
vector<int> G2[150000*2];
int F[150000*2];
int A[2000];
int D[150000*2];
int C[2][150000*2];
inline int fg(P p) {
int x = p._2, e = p._1;
if (G[x][0]._1 == e) return x+N;
else return x;
}
int bfs(int s) {
queue<int> q;
rep(i, 2*N) D[i] = INF;
D[s] = 0;
q.push(s);
int ret = INF;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int t : G2[x]) {
if (t == s) ret = min(ret, D[x]+1);
if (D[t] > D[x]+1) {
D[t] = D[x]+1;
q.push(t);
}
}
}
return ret;
}
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, 2*N) G2[i].clear();
rep(i, N) {
F[i] = fg(G[i][0]);
F[i+N] = fg((G[i].size()>=2)? G[i][1] : G[i][0]);
}
rep(i, 2*N) G2[F[i]].pb(i);
vector<int> S[2];
int r[2];
r[0] = bfs(T ); rep(i, N) S[0].pb(D[i]); sort(all(S[0]), greater<int>());
r[1] = bfs(T+N); rep(i, N) S[1].pb(D[i]); sort(all(S[1]), greater<int>());
rep(i, 2) rep(t, 2*N) C[i][t] = 0;
vector<P> qs;
rep(i, Q) qs.pb(P(g[i], i));
sort(all(qs));
rep(_, Q) {
int k = qs[_]._1, q = qs[_]._2;
int ctr = 0;
rep(i, 2) {
while (!S[i].empty() && S[i].back() <= k) {
int t = S[i].back();
if (r[i] != INF) C[i][t%r[i]]++;
else if (t == k) ctr++;
S[i].pop_back();
}
}
rep(i, 2) if (r[i] != INF) ctr += C[i][k%r[i]];
A[q] = ctr;
}
rep(i, Q) answer(A[i]);
}
