/*
ребра как вершины
*/
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
clock_t start;
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const int MAXN = 150005;
int n, m, q, p;
//__________________
vector <pii> edges;
vector <pii> g[MAXN];
map <pii, int> mp;
vector <int> eg[MAXN * 2]; // edge graph
vector <int> reg[MAXN * 2];
pii from_to[MAXN * 2];
int mn1, mn2;
vector <int> pr, siz;
vector <int> lst;
vector <bool> cycle;
vector <int> used;
int tiktak = 0;
vector <int> tin, tout;
vector <int> cycle_root;
vector <int> dist;
vector <int> cycle_size;
vector <vector<int>> mn_dist;
//__________________
int findp(int v) {
if (v == pr[v]) {
return v;
}
return pr[v] = findp(pr[v]);
}
void unite(int a, int b) {
a = findp(a);
b = findp(b);
if (a == b) {
return;
}
if (siz[a] > siz[b]) {
swap(a, b);
}
pr[a] = b;
siz[b] += siz[a];
}
bool find_cycle(int v) {
used[v] = 1;
for (int to : eg[v]) {
if (!used[to]) {
lst[to] = v;
bool f = find_cycle(to);
if (f) {
return true;
}
}
if (used[to] == 1) {
int fn = v;
while (fn != to) {
cycle[fn] = true;
fn = lst[fn];
}
cycle[to] = true;
return true;
}
}
used[v] = 2;
return false;
}
void rev_dfs(int v, int root, int len = 0) {
tin[v] = ++tiktak;
cycle_root[v] = root;
dist[v] = len;
for (int to : reg[v]) {
if (!cycle[to]) {
rev_dfs(to, root, len + 1);
}
}
tout[v] = tiktak;
}
void cycle_dfs(int v, int type, int len = 0) {
mn_dist[type][v] = len;
for (int to : eg[v]) {
if (mn_dist[type][to] == -1) {
cycle_dfs(to, type, len + 1);
}
}
}
bool father(int a, int b) {
return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
void calc(vector <int> comp) {
find_cycle(comp[0]);
int CYCLE_SIZE = 0;
for (int el : comp) {
if (cycle[el]) {
rev_dfs(el, el);
CYCLE_SIZE++;
}
}
for (int el : comp) {
cycle_size[el] = CYCLE_SIZE;
}
cycle_dfs(mn1, 1);
cycle_dfs(mn2, 2);
for (int type = 1; type <= 2; type++) {
for (int el : comp) {
if (cycle[el]) {
mn_dist[type][el] = (cycle_size[el] - mn_dist[type][el]) % cycle_size[el];
assert(mn_dist[type][el] < cycle_size[el]);
}
}
}
}
bool ok(int v, int k) {
if (!cycle[mn1]) {
if (father(mn1, v)) {
int up = dist[mn1];
int down = dist[v];
if (down - up == k) {
exit(0);
return true;
}
}
} else if (pr[v] == pr[mn1]) {
int h = dist[v];
int my_root = cycle_root[v];
if (k >= h + mn_dist[1][my_root] && (k - h - mn_dist[1][my_root]) % cycle_size[my_root] == 0) {
return true;
}
}
if (!cycle[mn2]) {
if (father(mn2, v)) {
int up = dist[mn2];
int down = dist[v];
if (down - up == k) {
return true;
}
}
} else if (pr[v] == pr[mn2]) {
int h = dist[v];
int my_root = cycle_root[v];
if (k >= h + mn_dist[2][my_root] && (k - h - mn_dist[2][my_root]) % cycle_size[my_root] == 0) {
return true;
}
}
return false;
}
void precalc(int sz) {
mn1 = g[p][0].sc;
if (szof(g[p]) > 1) {
mn2 = g[p][1].sc;
} else {
mn2 = mn1;
}
mn_dist.resize(3);
for (int i = 1; i <= 2; i++) {
mn_dist[i].resize(sz, -1);
}
cycle_size.resize(sz);
dist.resize(sz);
cycle_root.resize(sz);
pr.resize(sz);
siz.resize(sz);
lst.resize(sz);
used.resize(sz, 0);
cycle.resize(sz, false);
tin.resize(sz);
tout.resize(sz);
for (int i = 0; i < sz; i++) {
pr[i] = i;
siz[i] = 1;
lst[i] = -1;
}
for (int i = 0; i < sz; i++) {
for (int to : eg[i]) {
unite(i, to);
reg[to].pb(i);
}
}
vector <pii> vec;
for (int i = 0; i < sz; i++) {
vec.pb({findp(i), i});
}
sort(all(vec));
for (int i = 0; i < sz; i++) {
int r = i;
while (r < sz && vec[r].fr == vec[i].fr) {
r++;
}r--;
vector <int> comp;
for (int j = i; j <= r; j++) {
comp.pb(vec[j].sc);
}
calc(comp);
i = r;
}
}
pii para(int pos) {
int x = from_to[pos].fr, y = from_to[pos].sc;
pii res = {min(x, y), max(x, y)};
return res;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
start = clock();
n = N;
m = M;
q = Q;
p = P;
for (int i = 0; i < m; i++) {
int x = R[i][0];
int y = R[i][1];
edges.pb({x, y});
if (szof(g[x]) < 2) {
g[x].pb({y, i});
}
if (szof(g[y]) < 2) {
g[y].pb({x, i});
}
}
int cnt = 0;
vector <pii> edges;
for (int v = 0; v < n; v++) {
for (auto &edge : g[v]) {
edges.pb({v, edge.fr});
}
}
sort(all(edges));
auto get_pos = [&](pii x) {
int pos = lower_bound(all(edges), x) - edges.begin();
return pos;
};
for (int i = 0; i < szof(edges); i++) {
int v = edges[i].fr, to = edges[i].sc;
from_to[i] = {v, to};
}
for (int v = 0; v < n; v++) {
for (auto &edge : g[v]) {
edge.sc = get_pos({v, edge.fr});
}
}
int sz = 0;
for (int v = 0; v < n; v++) {
for (auto edge : g[v]) {
sz++;
int to = edge.fr, ind = edge.sc;
if (szof(g[to]) == 1) {
eg[ind].pb(mp[{to, v}]);
continue;
}
pii cur = para(ind);
pii mn1 = para(get_pos({to, g[to][0].fr}));
pii mn2 = para(get_pos({to, g[to][1].fr}));
if (cur != mn1) {
eg[ind].pb(mp[{to, g[to][0].fr}]);
} else {
eg[ind].pb(mp[{to, g[to][1].fr}]);
}
}
}
precalc(sz);
//dasdasdsadadsaldksakokjdosaihdujahiduhasiudhsahdijujsahdiuashgdihsagdijsahdisahdhsaijdhas
int ans;
for (int i = 0; i < q; i++) {
ans = 0;
for (int v = 0; v < n; v++) { // не забыть
int V = g[v][0].sc, k = G[i];
if (!cycle[mn1]) {
if (father(mn1, V)) {
int up = dist[mn1];
int down = dist[V];
if (down - up == k) {
ans++;
continue;
}
}
} else if (pr[V] == pr[mn1]) {
int h = dist[V];
int my_root = cycle_root[V];
if (k >= h + mn_dist[1][my_root] && (k - h - mn_dist[1][my_root]) % cycle_size[my_root] == 0) {
ans++;
continue;
}
}
if (!cycle[mn2]) {
if (father(mn2, V)) {
int up = dist[mn2];
int down = dist[V];
if (down - up == k) {
ans++;
continue;
}
}
} else if (pr[V] == pr[mn2]) {
int h = dist[V];
int my_root = cycle_root[V];
if (k >= h + mn_dist[2][my_root] && (k - h - mn_dist[2][my_root]) % cycle_size[my_root] == 0) {
ans++;
continue;
}
}
}
answer(ans);
}
}
