#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 3e5 + 5;
int n, m, p;
bool was[N], h[N];
int go[N];
vector < int > come[N];
vector < ii > v[N];
vector < int > cycle;
int findCycle(int x) {
h[x] = 1;
cycle.push_back(x);
if(!h[go[x]])
return findCycle(go[x]);
return go[x];
}
int curOut, curSize, cycleCnt, tme;
int out[N], dep[N], cycleSize[N], whichCycle[N], st[N], nd[N], onCycle[N];
void dfs(int x, int d) {
h[x] = 1;
st[x] = ++tme;
whichCycle[x] = cycleCnt;
out[x] = curOut;
dep[x] = d;
cycleSize[x] = curSize;
foreach(it, come[x]) {
int u = *it;
if(!h[u])
dfs(u, d + 1);
}
nd[x] = tme;
}
void init() {
for(int i = 1; i <= n; i++) {
for(int it = 0; it < v[i].size(); it++) {
int u = v[i][it].first;
int e = v[i][it].second;
was[i + (it * n)] = 1;
if(e == v[u][0].second and v[u].size() > 1) {
go[i + (it * n)] = u + n;
come[u + n].push_back(i + (it * n));
}
else {
go[i + (it * n)] = u;
come[u].push_back(i + (it * n));
}
}
}
for(int i = 1; i <= 2 * n; i++) {
//printf("go[%d] = %d\n", i, go[i]);
}
for(int i = 1; i <= 2 * n; i++)
onCycle[i] = -1;
for(int i = 1; i <= 2 * n; i++) {
if(was[i] and !h[i]) {
cycleCnt++;
cycle.clear();
int cyc = findCycle(i);
foreach(it, cycle) {
int x = *it;
h[x] = 0;
}
reverse(cycle.begin(), cycle.end());
while(cycle.back() != cyc)
cycle.pop_back();
reverse(cycle.begin(), cycle.end());
for(int it = 0; it < cycle.size(); it++) {
onCycle[cycle[it]] = it;
}
foreach(it, cycle) {
int x = *it;
h[x] = 1;
}
curSize = cycle.size();
foreach(it, cycle) {
int x = *it;
curOut = x;
dfs(x, 0);
}
}
}
}
bool check(int x, int y, int k) {
if(whichCycle[x] != whichCycle[y])
return 0;
if(onCycle[y] == -1) {
if(out[x] == out[y] and st[y] <= st[x] and st[x] <= nd[y])
return dep[x] - dep[y] == k;
return 0;
}
int dist = dep[x], size = cycleSize[x];
x = out[x];
x = onCycle[x];
y = onCycle[y];
if(x <= y)
dist += y - x;
else
dist += size - x + y;
if(dist > k)
return 0;
return (k - dist) % size == 0;
}
int solve(int x) {
int ans = 0;
for(int i = 1; i <= n; i++) {
bool flag = 0;
flag |= check(i, p, x);
if(was[p + n])
flag |= check(i, p + n, x);
ans += flag;
}
return ans;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N;
m = M;
p = P + 1;
for(int i = 0; i < M; i++) {
int x = R[i][0] + 1;
int y = R[i][1] + 1;
if(v[x].size() < 2)
v[x].push_back(ii(y, i));
if(v[y].size() < 2)
v[y].push_back(ii(x, i));
}
init();
for(int i = 0; i < Q; i++) {
answer(solve(G[i]));
}
}
