#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1.5e5 + 5, inf = 2e9 + 5;
struct ans { int a, b; ans(int A = inf-1, int B = inf):a(A), b(B) {} };
int d[2][maxn*2], len[2], cnt[maxn * 2];
vector<int> g[maxn*2];
void dfs(int u, int i)
{
for (int v : g[u])
{
if (d[i][v] != inf)
{
if (d[i][v] == 0) len[i] = d[i][u] + 1;
continue;
}
d[i][v] = d[i][u] + 1;
dfs(v, i);
}
}
void count_routes(int n, int m, int p, int e[][2], int q, int qu[])
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < 2; j++)
{
int u = e[i][j], v = e[i][j^1];
if (cnt[u] < 2) g[v + (cnt[v] == 0) * n].push_back(u + cnt[u] * n);
}
for (int j = 0; j < 2; j++) cnt[e[i][j]]++;
}
for (int i = 0; i < n; i++)
{
if (cnt[i] >= 2) continue;
for (int j : g[i+n]) g[i].push_back(j);
g[i+n].clear();
}
for (int l = 0; l < 2; l++)
{
fill(d[l], d[l] + maxn * 2, inf); len[l] = inf;
d[l][l*n+p] = 0;
dfs(l*n+p, l);
}
for (int i = 0; i < q; i++)
{
int cnt = 0;
for (int j = 0; j < n; j++)
{
bool ok = false;
for (int l = 0; l < 2; l++)
if (d[l][j] <= qu[i] && (qu[i] - d[l][j]) % len[l] == 0) ok = true;
cnt += ok;
}
answer(cnt);
}
}
