/*
ребра как вершины
*/
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#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];
struct Graph {
//__________________
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) {
//cout << "here" << endl;
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) {
//cout << "el: " << el << endl;
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]) {
//if (mn_dist[type][el] == -1) {
//assert(false);
//}
if (el == 1) {
//cout << "dasdadsadsdasda : " << from_to[el].fr << " " << from_to[el].sc << endl;
}
mn_dist[type][el] = (n - mn_dist[type][el]) % n;
}
}
}
}
bool ok(int v, int k) { // текущая вершина v, надо пройти еще k
// get mn1
//cout << "edge: " << from_to[v].fr << "->" << from_to[v].sc << endl;
//cout << "v k " << v << " " << k << endl;
if (!cycle[mn1]) {
if (father(mn1, v)) {
int up = dist[mn1];
int down = dist[v];
// down >= up
if (down - up == k) {
//cout << "wtf1: " << endl;
exit(0);
return true;
}
}
} else if (findp(v) == findp(mn1)) { // mn1 в цикле
int h = dist[v];
//cout << "\nh: " << h << endl;
int my_root = cycle_root[v];
//cout << "my: " << from_to[v].fr << " " << from_to[v].sc << endl;;
//cout << "dist: " << mn_dist[1][my_root] << endl;
//exit(0);
//cout << "otvet: " << (k - h - mn_dist[1][my_root]) << endl;
//cout << "n: " << n << endl;
if (k >= h + mn_dist[1][my_root] && (k - h - mn_dist[1][my_root]) % cycle_size[my_root] == 0) {
//cout << "wtf2 " << endl;
//exit(0);
return true;
}
}
// get mn2
if (!cycle[mn2]) {
if (father(mn2, v)) {
int up = dist[mn2];
int down = dist[v];
// down >= up
if (down - up == k) {
return true;
}
}
} else if (findp(v) == findp(mn2)) {
int h = dist[v];
int my_root = cycle_root[v];
//cout << "my: " << from_to[v].fr << " " << from_to[v].sc << endl;
//cout << "h: " << h << endl;
//cout << "dist: " << mn_dist[2][my_root] << endl;
//cout << "mn2: " << mn2 << endl;
//cout << "! " << from_to[mn2].fr << " " << from_to[mn2].sc << endl;
if (k >= h + mn_dist[2][my_root] && (k - h - mn_dist[2][my_root]) % n == 0) {
//cout << "eq3eaadasdassdasdasd " << endl;
return true;
}
}
return false;
}
Graph(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);
//cout << " " << "(" << from_to[i].fr << " " << from_to[i].sc << ")" << " ("
//<< from_to[to].fr << " " << from_to[to].sc << ")\n";
}
}
vector <pii> vec; // boss | vertex
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;
}
}
};
//void answer(int x) {
//cout << "ans: " << x << endl;
//}
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[]) {
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;
for (int v = 0; v < n; v++) {
for (auto &edge : g[v]) {
int to = edge.fr, ind = edge.sc;
mp[{v, to}] = cnt++;
from_to[cnt - 1] = {v, to};
edge.sc = cnt - 1;
}
}
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(mp[{to, g[to][0].fr}]);
pii mn2 = para(mp[{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}]);
}
}
}
Graph graph(sz);
int ans;
for (int i = 0; i < q; i++) {
ans = 0;
for (int v = 0; v < n; v++) { // не забыть
//cout << v << " -> " << g[v][0].fr << ": " << graph.ok(g[v][0].sc, G[i]) << endl;
ans += graph.ok(g[v][0].sc, G[i]);
}
answer(ans);
}
}
//static int N, M, P, Q;
//static int R[MAXN][2];
//static int G[MAXN];
//signed main() {
//cin >> N >> M >> P;
//for (int i = 0; i < M; i++) {
//cin >> R[i][0] >> R[i][1];
//}
//cin >> Q;
//for (int i = 0; i < Q; i++) {
//cin >> G[i];
//}
//count_routes(N, M, P, R, Q, G);
//}
/*
3 3 0
0 1
0 2
1 2
1
1
*/
