#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef pair<int, int> pii;
const int N = 1.5e5 + 2;
const int INF = 1e9 + 1;
int n, m, src;
pii org[2];
vector<int> g[N];
stack<pii> st;
map<pii, int> vst, f[2], r[2];
vector<pair<pii, pii> > a;
void Dfs(int u, int p)
{
pii pre(p, u);
pii e(u, g[u].size() > 1 && g[u][0] == p ? g[u][1] : g[u][0]);
f[0][pre] = f[1][pre] = -1;
if (vst.find(e) == vst.end())
{
vst[e] = 1;
st.push(e);
Dfs(e.second, u);
vst[e] = 2;
r[0][pre] = r[0][e];
r[1][pre] = r[1][e];
if (pre == org[0]) f[0][pre] = 0;
else if (f[0][e] != -1) f[0][pre] = f[0][e] + 1;
if (pre == org[1]) f[1][pre] = 0;
else if (f[1][e] != -1) f[1][pre] = f[1][e] + 1;
}
else if (vst[e] == 1)
{
for (int i = 0; ;++i)
{
auto top = st.top(); st.pop();
if (top == org[0]) f[0][pre] = i;
if (top == org[1]) f[1][pre] = i;
++r[0][pre];
++r[1][pre];
if (top == e) break;
}
if (f[0][pre] == -1) r[0][pre] = -1;
else f[0][pre] = (r[0][pre] - f[0][pre]) % r[0][pre];
if (f[1][pre] == -1) r[1][pre] = -1;
else f[1][pre] = (r[1][pre] - f[1][pre]) % r[1][pre];
}
else
{
r[0][pre] = r[0][e];
r[1][pre] = r[1][e];
if (pre == org[0]) f[0][pre] = 0;
else if (f[0][e] != -1) f[0][pre] = f[0][e] + 1;
if (pre == org[1]) f[1][pre] = 0;
else if (f[1][e] != -1) f[1][pre] = f[1][e] + 1;
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N, m = M, src = P;
for (int i = 0; i < m; ++i)
{
int u, v; u = R[i][0], v = R[i][1];
if (g[u].size() < 2) g[u].push_back(v);
if (g[v].size() < 2) g[v].push_back(u);
}
org[0] = {src, g[src][0]};
org[1] = {src, g[src].size() > 1 ? g[src][1] : -1};
for (int u = 0; u < n; ++u)
{
while (!st.empty()) st.pop();
pii e(u, g[u][0]);
if (vst.find(e) == vst.end()) Dfs(u, -1);
a.push_back({{f[0][e], r[0][e]}, {f[1][e], r[1][e]}});
//cerr << f[0][e] << ' ' << r[0][e] << ' ' << f[1][e] << ' ' << r[1][e] << '\n';
}
int q = Q;
for (int i = 0; i < q; ++i)
{
int x = G[i], ans = 0;
for (auto p: a)
{
auto satis = [](int x, pii q) -> bool { return q.first != -1 && (x == q.first || (x > q.first && q.second != -1 && (x - q.first) % q.second == 0)); };
ans += satis(x, p.first) || satis(x, p.second);
}
answer(ans);
}
}
