/** - dwuy -
／＞ フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5e8;
const int MX = 350005;
int n, m, P;
int L1, L2;
int deg[MX];
int nxt[MX];
int dis1[MX];
int dis2[MX];
vector<int> rG[MX];
void dfs1(int u){
for(int v: rG[u]) if(dis1[v] > dis1[u] + 1){
dis1[v] = dis1[u] + 1;
dfs1(v);
}
}
void dfs2(int u){
for(int v: rG[u]) if(dis2[v] > dis2[u] + 1){
dis2[v] = dis2[u] + 1;
dfs2(v);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int QR[]){
n = N;
m = M;
::P = ++P;
memset(nxt, -1, sizeof nxt);
for(int i=0; i<m; i++) deg[R[i][0] + 1]++, deg[R[i][1] + 1]++;
for(int i=0; i<m; i++){
int u = R[i][0] + 1;
int v = R[i][1] + 1;
if(nxt[u] == -1) nxt[u] = deg[v] > 1 && nxt[v] == -1? v + n : v;
else if(nxt[u + n] == -1) nxt[u + n] = deg[v] > 1 && nxt[v] == -1? v + n : v;
if(nxt[v] == -1) nxt[v] = deg[u] > 1 && nxt[u] == v + n? u + n : u;
else if(nxt[v + n] == -1) nxt[v + n] = deg[u] > 1 && nxt[u] == v? u + n : u;
}
for(int i=1; i<=n+n; i++) rG[nxt[i]].push_back(i);
memset(dis1, 0x3f, sizeof dis1);
memset(dis2, 0x3f, sizeof dis2);
dis1[P] = dis2[P + n] = 0;
dfs1(P);
dfs2(P + n);
int L1 = INF;
int L2 = INF;
for(int u=P, i=1; i<=n+n; i++){
u = nxt[u];
if(u == P){
L1 = i;
break;
}
}
for(int u=P+n, i=1; i<=n+n; i++){
u = nxt[u];
if(u == P + n){
L2 = i;
break;
}
}
for(int i=0; i<Q; i++){
int k = QR[i];
int ans = 0;
for(int i=1; i<=n; i++){
if(k >= dis1[i] && (k - dis1[i])%L1 == 0) ans++;
else if(k >= dis2[i] && (k - dis2[i])%L2 == 0) ans++;
}
answer(ans);
}
}
/*
6 8 0
1 3
0 2
3 5
0 4
4 3
2 5
4 1
2 3
10
1 8 192 384 3476 9483 23417 332764 342 46
*/
