#include "garden.h"
#include "gardenlib.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 10000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001
using namespace std;
vec<vec<pii>> g;
vec<vec<vec<ll>>> dist;
vec<vec<bool>> bol;
/*
void answer(ll x) {
cout << x << '\n';
return;
}
*/
ll dfs(ll x, ll pr, ll typ) {
if (g[x].size() == 1) pr = -1;
For(i, g[x].size()) {
if (g[x][i].ss == pr) continue;
if (bol[x][i]) return dist[x][i][typ];
bol[x][i] = 1;
dist[x][i][typ] = dfs(g[x][i].ff, g[x][i].ss, typ) + 1;
return dist[x][i][typ];
}
}
void count_routes(int n, int m, int p, int r[][2], int q, int pq[]) {
g.resize(n);
dist.resize(n, vec<vec<ll>>(2, vec<ll>(2, (-1) * NEK)));
For(i, m) {
if (g[r[i][0]].size() != 2) {
g[r[i][0]].push_back({ r[i][1], i });
}
if (g[r[i][1]].size() != 2) {
g[r[i][1]].push_back({ r[i][0], i });
}
}
bol.clear();
bol.resize(n, vec<bool>(2, false));
dist[p][0][0] = 0;
dist[p][1][1] = 0;
bol[p][0] = 1;
For(i, n) {
//0->mozes pouzit najdrahsieho
dfs(i, -1, 0);
if(i != p) dfs(i, g[i][0].ss, 0);
}
bol.clear();
bol.resize(n, vec<bool>(2, false));
bol[p][1] = 1;
For(i, n) {
if(i != p) dfs(i, -1, 1);
dfs(i, g[i][0].ss, 1);
if (g[i].size() == 1) {
dist[i][1][0] = dist[i][0][0];
dist[i][1][1] = dist[i][0][1];
}
}
vec<pii> o;
For(i, q) {
o.push_back({ pq[i], i });
}
sort(o.begin(), o.end());
vec<vec<ll>> pp(2);
For(i, n) {
For(j, 2) {
if (dist[i][0][j] < 0) continue;
pp[j].push_back(dist[i][0][j]);
}
}
sort(pp[0].begin(), pp[0].end());
sort(pp[1].begin(), pp[1].end());
vec<ll> vys(q, 0);
//vyries pripad ze vychadza iba 1 hrana
//zaciatok divneho pripadu
if (g[p].size() == 1) {
ll jtyp = 0;
if (g[g[p][0].ff][0].ss == g[p][0].ss) jtyp = 1;
ll q1 = dist[g[p][0].ff][jtyp][0] + 1;
ll som = 0;
vec<ll> zv(q1 + 1, 0);
For(i, o.size()) {
while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
zv[pp[0][som] % q1]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % q1];
}
For(i, q) {
answer(vys[i]);
}
return;
}
//koniec divneho pripadu
ll sit1 = 0;
ll q11, q12;
ll jtyp = 0;
if (g[g[p][0].ff][0].ss == g[p][0].ss) jtyp = 1;
q11 = dist[g[p][0].ff][jtyp][0] + 1;
q12 = dist[g[p][0].ff][jtyp][1] + 1;
ll q21, q22;
jtyp = 0;
pii dh = g[p][1];
if (g[dh.ff][0].ss == dh.ss) jtyp = 1;
q21 = dist[dh.ff][jtyp][0] + 1;
q22 = dist[dh.ff][jtyp][1] + 1;
//situacia 4
if (q12 > 0 && q21 > 0) {
ll q1 = q12;
ll q2 = q21;
ll som = 0;
vec<ll> zv(q1 + q2 + 1, 0);
som = 0;
For(i, o.size()) {
while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
zv[pp[0][som] % (q1 + q2)]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % (q1 + q2)];
}
som = 0;
zv.clear();
zv.resize(q1 + q2 + 1, 0);
For(i, o.size()) {
while (som < pp[1].size() && pp[1][som] <= o[i].ff) {
zv[pp[1][som] % (q1 + q2)]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % (q1 + q2)];
}
For(i, q) {
answer(vys[i]);
}
return;
}
//situacia 1
if (q11 > 0 && q22 > 0) {
ll q1 = q11;
ll q2 = q22;
ll som = 0;
vec<ll> zv(q1 + 1, 0);
For(i, o.size()) {
while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
zv[pp[0][som] % q1]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % q1];
}
som = 0;
zv.clear();
zv.resize(q2 + 1, 0);
For(i, o.size()) {
while (som < pp[1].size() && pp[1][som] <= o[i].ff) {
zv[pp[1][som] % q2]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % q2];
}
For(i, q) {
answer(vys[i]);
}
return;
}
//situacia 2
if (q12 > 0 && q22 > 0) {
ll q1 = q12;
ll q2 = q22;
ll som = 0;
vec<ll> zv(q2 + 1, 0);
vec<ll> poc(3 * n, 0);
For(i, pp[0].size()) {
poc[pp[0][i]]++;
}
For(i, o.size()) {
if (o[i].ff < poc.size()) vys[o[i].ss] += poc[o[i].ff];
}
som = 0;
zv.clear();
zv.resize(q2 + 1, 0);
For(i, o.size()) {
while (som < pp[1].size() && pp[1][som] <= o[i].ff) {
zv[pp[1][som] % q2]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % q2];
}
For(i, q) {
answer(vys[i]);
}
return;
}
//situacia 3
if (q11 > 0 && q21 > 0) {
ll q1 = q11;
ll q2 = q21;
ll som = 0;
vec<ll> zv(q1 + 1, 0);
For(i, o.size()) {
while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
zv[pp[0][som] % q1]++;
som++;
}
vys[o[i].ss] += zv[o[i].ff % q1];
}
som = 0;
zv.clear();
zv.resize(q2 + 1, 0);
vec<ll> poc(3 * n, 0);
For(i, pp[1].size()) {
poc[pp[1][i]]++;
}
For(i, o.size()) {
if(o[i].ff < poc.size()) vys[o[i].ss] += poc[o[i].ff];
}
For(i, q) {
answer(vys[i]);
}
return;
}
return;
}
/*
int main() {
while (true) {
int n1, m1, p1, r1[1000][2], q1, g1[1000];
//cin >> n1 >> m1 >> p1;
n1 = rand() % 10 + 2;
m1 = rand() % 10 + n1;
p1 = rand() % n1;
For(i, n1) {
//cin >> r1[i][0] >> r1[i][1];
r1[i][0] = i;
r1[i][1] = rand() % n1;
}
For(i, m1 - n1) {
while (true) {
r1[i + n1][0] = rand() % n1;
r1[i + n1][1] = rand() % n1;
if (r1[i + n1][0] != r1[i + n1][1]) break;
}
}
//cin >> q1;
q1 = 1;
For(i, q1) {
//cin >> g1[i];
g1[i] = rand() % 1000000000;
}
cout << n1 << ' ' << m1 << ' ' << p1 << '\n';
For(i, m1) {
cout << r1[i][0] << ' ' << r1[i][1] << '\n';
}
cout << q1 << '\n';
For(i, q1) {
cout << g1[i] << '\n';
}
count_routes(n1, m1, p1, r1, q1, g1);
}
return 0;
}*/
