#include <bits/stdc++.h>
using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define readv(v) do { for(auto &i: v) cin >> i; } while(0)
#define writev(v) do { for(auto i: v) cout << i << " "; } while(0)
#define _ << " " <<
#define ll long long
#define u64 unsigned long long
#ifndef MARCO
bool dbg = 0;
#define info(str, ...)
#define infon(str, ...)
#else
bool dbg = 1;
#define info(str, ...) do { fprintf(stderr, "\033[31m" str "\033[0m", ##__VA_ARGS__); } while(0)
#define infon(str, ...) do { fprintf(stderr, "\033[31m" str "\033[0m\n", ##__VA_ARGS__); } while(0)
#endif
constexpr int LOG = 30;
#define int long long
struct cycle{
ll T, q; //ans = q + k*T
bool operator==(const cycle &o) const {
return (T == o.T) & (q == o.q);
}
};
cycle lost = {-1, -1};
int N, P, Q;
vector<cycle> rgood, rbad; //risposta se arrivo in quel nodo dall'arco più bello o no
vector<int> onegood, onebad;
vector<int> G1, G2;
vector<int> statgood, statbad; //0 = mai visto, >0 = in esecuzione, -1 = finito
int esplorabad(int a, int b, int c);
int esploragood(int a, int b, int c);
int esplorabad(int n, int k, int seenP) {
if(n == P) seenP = 0;
if(statbad[n] == -1) return 0;
if(statbad[n] > 0) {
//il ciclo ha lunghezza k-statbad[n]
if(seenP < 0) rbad[n] = lost;
else rbad[n] = {k - statbad[n], k - statbad[n] - seenP};
statbad[n] = -1;
return 1;
}
statbad[n] = k;
int n2 = G2[n];
if(n == G1[n2] && G2[n2] != -1) {
int rtn;
if(esplorabad(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
if(rbad[n2] == lost) rbad[n] = lost;
else rbad[n] = {rbad[n2].T, rbad[n2].q+1};
statbad[n] = -1;
rtn = 0;
}
else { //dentro un ciclo
rtn = 1;
if(statbad[n] == -1) rtn = 0; //fine del ciclo
else if(rbad[n2] == lost) rbad[n] = lost;
else rbad[n] = {rbad[n2].T, (rbad[n2].q+1)%rbad[n2].T};
statbad[n] = -1;
}
if(seenP == 0) onebad[n] = 0;
else onebad[n] = onebad[n2]+1;
return rtn;
}
else {
int rtn;
if(esploragood(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
if(rgood[n2] == lost) rbad[n] = lost;
else rbad[n] = {rgood[n2].T, rgood[n2].q+1};
statbad[n] = -1;
rtn = 0;
}
else { //dentro un ciclo
rtn = 1;
if(statbad[n] == -1) rtn = 0; //fine del ciclo
else if(rbad[n2] == lost) rbad[n] = lost;
else rbad[n] = {rgood[n2].T, (rgood[n2].q+1)%rgood[n2].T};
statbad[n] = -1;
}
if(seenP == 0) onebad[n] = 0;
else onebad[n] = onegood[n2]+1;
return rtn;
}
}
int esploragood(int n, int k, int seenP) {
if(n == P) seenP = 0;
if(statgood[n] == -1) return 0;
if(statgood[n] > 0) {
//il ciclo ha lunghezza k-statgood[n]
if(seenP < 0) rgood[n] = lost;
else rgood[n] = {k - statgood[n], k - statgood[n] - seenP};
statgood[n] = -1;
return 1;
}
statgood[n] = k;
int n2 = G1[n];
if(n == G1[n2] && G2[n2] != -1) {
int rtn;
if(esplorabad(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
if(rbad[n2] == lost) rgood[n] = lost;
else rgood[n] = {rbad[n2].T, rbad[n2].q+1};
statgood[n] = -1;
rtn = 0;
}
else { //dentro un ciclo
rtn = 1;
if(statgood[n] == -1) rtn = 0; //fine del ciclo
else if(rbad[n2] == lost) rgood[n] = lost;
else rgood[n] = {rbad[n2].T, (rbad[n2].q+1)%rbad[n2].T};
statgood[n] = -1;
}
if(seenP == 0) onegood[n] = 0;
else onegood[n] = onebad[n2]+1;
return rtn;
}
else {
int rtn;
if(esploragood(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
if(rgood[n2] == lost) rgood[n] = lost;
else rgood[n] = {rgood[n2].T, rgood[n2].q+1};
statgood[n] = -1;
rtn = 0;
}
else { //dentro un ciclo
rtn = 1;
if(statgood[n] == -1) rtn = 0; //fine del ciclo
else if(rbad[n2] == lost) rgood[n] = lost;
else rgood[n] = {rgood[n2].T, (rgood[n2].q+1)%rgood[n2].T};
statgood[n] = -1;
}
if(seenP == 0) onegood[n] = 0;
else onegood[n] = onegood[n2]+1;
return rtn;
}
}
signed main(){
#ifndef MARCO
ios::sync_with_stdio(false);
cin.tie(nullptr);
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
int M;
cin >> N >> M >> P;
G1.resize(N, -1);
G2.resize(N, -1);
for(int i=0; i<M; i++) {
int a, b; cin >> a >> b;
if(G1[a] == -1) G1[a] = b;
else if(G2[a] == -1) G2[a] = b;
swap(a, b);
if(G1[a] == -1) G1[a] = b;
else if(G2[a] == -1) G2[a] = b;
}
rgood.resize(N);
rbad.resize(N);
statgood.resize(N);
statbad.resize(N);
onegood.resize(N, -1e9);
onebad.resize(N, -1e9);
for(int i=N-1; i>=0; i--) {
esploragood(i, 1, -1e9);
}
if(dbg) {
infon("\ndebugging...");
infon("rgood:");
info("T: "); for(int i=0; i<N; i++) cout << rgood[i].T << " "; cout << "\n";
info("q: "); for(int i=0; i<N; i++) cout << rgood[i].q << " "; cout << "\n";
infon("rbad:");
info("T: "); for(int i=0; i<N; i++) cout << rbad[i].T << " "; cout << "\n";
info("q: "); for(int i=0; i<N; i++) cout << rbad[i].q << " "; cout << "\n";
infon("onegood: ");
for(int i: onegood) cout << i << " "; cout << "\n";
infon("onebad: ");
for(int i: onebad) cout << i << " "; cout << "\n";
}
int Q; cin >> Q;
while(Q--) {
ll x; cin >> x;
int ans = 0;
int i=-1;
for(auto &[T, q]: rgood) {
i++;
if(onegood[i] == x) {
ans++;
continue;
}
if(T <= 0) continue;
if(x-q >= 0 && (x-q)%T == 0) ans++;
}
cout << ans << "\n";
}
}
