#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int MAXN = 150100, MAXK = 31;
int n, m, p;
vii adj[MAXN];
int par[2*MAXN][MAXK];
int getId (int v, int b) {
return (b*n + v);
}
int lift (int v, ll x) {
FOR(i, 0, MAXK-1)
if (x & (1ll<<i))
v = par[v][i];
return v;
}
int getAns (ll k){
int ret = 0;
//k--;
FOR(i, 0, n-1) {
int lifted = lift(i,k);
// cout << " k = " << k << " i = " << i << " lifted = " << lifted << endl;
if (lifted == getId(p, 0) || lifted == getId(p, 1)) {
ret++;
}
}
return ret;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P;
FOR(i, 0, m-1) {
int u = R[i][0];
int v = R[i][1];
adj[u].pb({i, v});
adj[v].pb({i, u});
}
FOR(v, 0, n-1) FOR(b, 0, 1) {
int fr = getId(v, b);
int u = (b < (int)adj[v].size() ? adj[v][b].s : adj[v][0].s);
int b2 = (adj[u][0].s == v);
int to = getId(u, b2);
par[fr][0] = to;
// cout << " fr = " << fr << " to = " << to << endl;
}
FOR(j, 1, MAXK-1) FOR(i, 0, getId(n-1, 1))
par[i][j] = par[par[i][j-1]][j-1];
for(int i=0; i<Q; i++) {
ll k = G[i];
int ans = getAns (k);
answer(ans);
}
}
