#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
#ifndef wambule
#include "garden.h"
#include "gardenlib.h"
#else
void answer(int x) {
cout << "[!] " << x << endl;
}
#endif
namespace blob {
int p, pp;
}
void G(int x, int x2[], int x4[], int x5[], int x6[], int x7[], int x8[], int x9[], int &z) {
x7[x] = z;
++z;
int y = x6[x];
if(x7[y]) {
if(x5[y]) {
x2[x] = -1;
if(x != blob::p) x4[x] = (x4[y] == -1 ? -1 : x4[y] + 1);
if(x != blob::pp) x9[x] = (x9[y] == -1 ? -1 : x9[y] + 1);
x5[x] = 1;
} else {
if(x7[blob::p] >= x7[y]) {
if(x != blob::p) x4[x] = x7[blob::p] - x7[y] + 1;
}
if(x7[blob::pp] >= x7[y]) {
if(x != blob::pp) x4[x] = x7[blob::pp] - x7[y] + 1;
}
x2[x] = x7[x] - x7[y] + 1;
x8[y] = 1;
}
x5[x] = 1;
return;
}
G(y, x2, x4, x5, x6, x7, x8, x9, z);
x2[x] = (x8[y] ? -1 : x2[y]);
if(x != blob::p) x4[x] = (x4[y] == -1 ? -1 : x4[y] + 1);
if(x != blob::pp) x9[x] = (x9[y] == -1 ? -1 : x9[y] + 1);
x5[x] = 1;
}
void count_routes(int n, int m, int p, int r[][2], int q, int gg[]) {
blob::p = p;
int pp = p + n;
blob::pp = pp;
int N = 2 * n;
int x2[N], x4[N], x5[N];
int x6[N], x7[N], x8[N], x9[N];
vint v[n];
for(int i = 0; i < N; ++i) {
x5[i] = x7[i] = x8[i] = 0;
x4[i] = (i == p ? 0 : -1);
x9[i] = (i == pp ? 0 : -1);
x2[i] = -1;
}
for(int i = 0; i < m; ++i) {
if(sz(v[r[i][0]]) < 2) v[r[i][0]].push_back(r[i][1]);
if(sz(v[r[i][1]]) < 2) v[r[i][1]].push_back(r[i][0]);
}
for(int i = 0; i < n; ++i) {
x6[i] = v[i][0];
x6[i + n] = v[i][(sz(v[i]) == 2)];
}
for(int i = 0; i < N; ++i) {
if(x6[x6[i]] == i || x6[x6[i]] == n + i) {
x6[i] = x6[i] + n;
}
}
///
// for(int i = 0; i < N; ++i) {
// cout << (i >= n ? i - n : i) << ", " << (i >= n) << " -> " << x6[i] << endl;
// }
///
int z = 1;
for(int i = 0; i < N; ++i) {
int x = i;
if(!x5[x]) {
G(x, x2, x4, x5, x6, x7, x8, x9, z);
}
}
for(int qi = 0; qi < q; ++qi) {
int g = gg[qi];
int ap = 0;
for(int i = 0; i < n; ++i) {
if(x2[p] == -1) {
if(x4[i] == g) {
++ap;
continue;
}
} else {
if(g >= x4[i]) {
if((g - x4[i]) % x2[p] == 0) {
++ap;
continue;
}
}
}
if(x2[pp] == -1) {
if(x9[i] == g) {
++ap;
continue;
}
} else {
if(g >= x9[i]) {
if((g - x9[i]) % x2[pp] == 0) {
++ap;
continue;
}
}
}
// cout << "[ O ] " << i << endl;
}
answer(ap);
}
}
#ifdef wambule
int n = 5;
int m = 5;
int p = 2;
int q = 2;
int g[] = {3, 1};
int r[][2] = {1, 0, 1, 2, 3, 2, 1, 3, 4, 2};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
count_routes(n, m, p, r, q, g);
return 0;
}
#endif
