#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
using ii = pair<int, int>;
int cur_scc;
vector<int> tp, scc_num, sz_scc, adj_from_0;
vector<bool> vis;
vector<vector<int> > adj, adj_t, adj_scc_t, init;
vector<vector<ii> > adj_2;
void dfs(int u) {
if (vis[u]) {
return;
}
vis[u] = 1;
for (auto v : adj_t[u]) {
dfs(v);
}
tp.pb(u);
}
void collect(int u) {
if (vis[u]) {
return;
}
vis[u] = 1;
scc_num[u] = cur_scc;
for (auto v : adj[u]) {
collect(v);
}
}
vector<int> dp(int u) {
vector<int> cur = init[u];
if ((int)cur.size() > 1) {
return cur;
}
for (auto v : adj_scc_t[u]) {
auto tmp = dp(v);
for (int i : tmp) {
bool in = 0;
for (int j : cur) {
if (i == j) {
in = 1;
break;
}
}
if (!in) {
cur.pb(i);
if ((int)cur.size() > 1) {
return cur;
}
}
}
}
return cur;
}
vector<int> cyc;
int find_cyc(int u, int e = -1) {
vis[u] = 1;
for (auto [v, idx] : adj_2[u]) {
if ((idx ^ 1) != e && vis[v]) {
cyc.pb(idx);
//~ cout << u << " --> " << v << endl;
//~ cout << u << " RET " << v << endl;
return v;
}
}
for (auto [v, idx] : adj_2[u]) if ((idx ^ 1) != e) {
int tmp = find_cyc(v, idx);
if (tmp != -1) {
if (tmp == -2) {
//~ path.pb(idx);
} else {
cyc.pb(idx);
if (tmp == u) {
tmp = -2;
}
}
//~ cout << u << " RET " << tmp << endl;
return tmp;
}
}
//~ cout << u << " RET " << -1 << endl;
return -1;
}
vector<int> path;
vector<bool> on_cyc;
bool find_path(int u) {
vis[u] = 1;
if (on_cyc[u]) {
return 1;
}
for (auto [v, idx] : adj_2[u]) {
if (!vis[v] && find_path(v)) {
path.pb(idx);
return 1;
}
}
return 0;
}
variant<bool, vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V) {
vis.resize(N);
scc_num.resize(N);
adj.resize(N);
adj_2.resize(N);
adj_t.resize(N);
adj_scc_t.resize(N);
for (int i = 0; i < M; i++) {
adj[U[i]].pb(V[i]);
adj_2[U[i]].eb(V[i], i);
adj_t[V[i]].pb(U[i]);
}
for (int i = 0; i < N; i++) {
dfs(i);
}
reverse(tp.begin(), tp.end());
fill(vis.begin(), vis.end(), 0);
for (int i : tp) {
if (!vis[i]) {
collect(i);
cur_scc++;
}
}
sz_scc.resize(cur_scc);
init.resize(cur_scc);
for (int i = 0; i < N; i++) {
sz_scc[scc_num[i]]++;
}
for (int i = 0; i < M; i++) {
if (U[i] == 0 && (int)init[scc_num[V[i]]].size() < 2) {
init[scc_num[V[i]]].pb(i);
}
if (scc_num[U[i]] != scc_num[V[i]]) {
adj_scc_t[scc_num[V[i]]].pb(scc_num[U[i]]);
}
}
for (int i = 0; i < cur_scc; i++) {
auto vec = dp(i);
if (sz_scc[i] > 1 && (int)vec.size() > 1) {
fill(vis.begin(), vis.end(), 0);
int any = -1;
for (int j = 0; j < N; j++) {
if (scc_num[j] == i) {
any = j;
break;
}
}
assert(any != -1);
find_cyc(any);
reverse(cyc.begin(), cyc.end());
for (auto &i : cyc) {
if (i == vec[0] || i == vec[1]) {
i ^= 1;
}
}
on_cyc.resize(N);
for (auto i : cyc) {
on_cyc[U[i]] = on_cyc[V[i]] = 1;
}
fill(vis.begin(), vis.end(), 0);
path.clear();
find_path(V[vec[0]]);
vector<int> ret;
path.pb(vec[0]);
reverse(path.begin(), path.end());
vector<int> prv_path = path;
for (auto i : path) {
ret.pb(i);
}
int cur_node = V[ret.back()];
int st = -1;
for (int i = 0; i < (int)cyc.size(); i++) {
if (U[cyc[i]] == cur_node) {
st = i;
break;
}
}
assert(st != -1);
auto nxt = [&](int x) {
return (x + 1) % (int)cyc.size();
};
ret.pb(cyc[st]);
for (int j = nxt(st); j != st; j = nxt(j)) {
ret.pb(cyc[j]);
}
reverse(path.begin(), path.end());
for (auto i : path) {
ret.pb(i);
}
fill(vis.begin(), vis.end(), 0);
path.clear();
find_path(V[vec[1]]);
path.pb(vec[1]);
sort(prv_path.begin(), prv_path.end());
for (auto &i : path) {
if (binary_search(prv_path.begin(), prv_path.end(), i)) {
i ^= 1;
}
}
reverse(path.begin(), path.end());
for (auto i : path) {
ret.pb(i);
}
cur_node = V[ret.back()];
st = -1;
for (int i = 0; i < (int)cyc.size(); i++) {
if (V[cyc[i]] == cur_node) {
st = i;
break;
}
}
assert(st != -1);
auto prv = [&](int x) {
if (x == 0) return (int)cyc.size() - 1;
else return x - 1;
};
ret.pb(cyc[st]);
for (int j = prv(st); j != st; j = prv(j)) {
ret.pb(cyc[j]);
}
reverse(path.begin(), path.end());
for (auto i : path) {
ret.pb(i);
}
return ret;
}
}
return false;
}
