///
/// There's a reason for your defeat, DIO. One simple reason...
/// You pissed me off.
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
#ifndef DARD
#include "garden.h"
#include "gardenlib.h"
#else
void answer(int x)
{
cout << x << ' ';
}
#endif
const int N = 150'010;
vector<int> T[2*N];
int A[2*N];
int deg[N], cnt[N];
void add_edge(int v, int u)
{
A[v] = u;
T[u].push_back(v);
}
int ans[N];
int q, g[N];
bool cyc[2*N];
void dfs(int v, int d)
{
cnt[d] += v >= N;
for (int u : T[v])
dfs(u, d+1);
}
vector<vector<int>> vmod;
int cycs;
void dfs2(int v, int d, int rt)
{
if (v >= N)
vmod[d%cycs].push_back(d);
for (int u : T[v])
if (u != rt)
dfs2(u, d+1, rt);
}
void solve(int v)
{
memset(cyc, 0, sizeof(cyc));
int u = v;
cycs = 0;
do {
cyc[u] = 1;
u = A[u];
++cycs;
} while (!cyc[u]);
if (u != v) {
memset(cnt, 0, sizeof(cnt));
dfs(v, 0);
Loop (i,0,q)
ans[i] += cnt[g[i]];
} else {
vmod.clear();
vmod.resize(cycs);
dfs2(v, 0, v);
Loop (i,0,cycs)
sort(vmod[i].begin(), vmod[i].end());
Loop (i,0,q) {
int gm = g[i]%cycs;
ans[i] += upper_bound(vmod[gm].begin(),
vmod[gm].end(), g[i]) - vmod[gm].begin();
}
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
Loop (i,0,m) {
deg[r[i][0]]++;
deg[r[i][1]]++;
}
Loop (i,0,m) {
for (auto [v, u] : {pii{r[i][0], r[i][1]}, pii{r[i][1], r[i][0]}}) {
if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] == 0) // F F
add_edge(v, u);
if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] != 0) // F nF
add_edge(v, u+N);
if (cnt[v] == 0 && cnt[u] == 0) // nF F
add_edge(v+N, u);
if (cnt[v] == 0 && cnt[u] != 0) // nF nF
add_edge(v+N, u+N);
}
cnt[r[i][0]]++;
cnt[r[i][1]]++;
}
::q = q;
Loop (i,0,q) ::g[i] = g[i];
solve(p);
solve(p+N);
Loop (i,0,q)
answer(ans[i]);
}
#ifdef DARD
int main()
{
// int constexpr n = 6;
// int constexpr m = 6;
// int constexpr p = 0;
// int constexpr q = 1;
// int g[q] = {3};
// int r[m][2] = {{1,2}, {0,1}, {0,3}, {3,4}, {4,5}, {1,5}};
int constexpr n = 5;
int constexpr m = 5;
int constexpr p = 2;
int constexpr q = 2;
int g[q] = {3, 1};
int r[m][2] = {{1,0}, {1,2}, {3,2}, {1,3}, {4,2}};
count_routes(n, m, p, r, q, g);
cout << '\n';
}
#endif
