#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
vector<pii> edges[MAXN];
vector<pii> redges[MAXN];
bool dead[MAXN];
int indeg[MAXN];
int outdeg[MAXN];
pii par[MAXN];
pii par2[MAXN];
pii edge_list[MAXN];
int n, m;
vector<int> path[2];
int cyc_node;
bool fin[MAXN];
bool vis[MAXN];
void prune(int i) {
dead[i] = 1;
if (indeg[i] == 0) {
return;
}
for (pii e: redges[i]) {
if (dead[e.first]) continue;
outdeg[e.first]--;
if (outdeg[e.first] == 0) prune(e.first);
}
indeg[i] = 0;
}
void make_path(int cur, vector<int> &cpath, bool spec = 1) {
if (spec == 1 && par2[cur].first != -1) {
make_path(par2[cur].first, cpath, 0);
cpath.push_back(par2[cur].second);
}
if (cur == 0) return;
make_path(par[cur].first, cpath, 0);
cpath.push_back(par[cur].second);
}
bool dfs(int cur) {
vis[cur] = 1;
for (pii e: edges[cur]) {
if (dead[e.first]) continue;
if (fin[e.first]) { // do things
make_path(e.first, path[0]);
make_path(cur, path[1]);
path[1].push_back(e.second);
cyc_node = e.first;
return 1;
}
if (vis[e.first]) {
if (outdeg[e.first] > 1) return 1;
// par2[e.first] = pii(cur, e.second);
continue;
}
par[e.first] = pii(cur, e.second);
if (dfs(e.first)) return 1;
}
fin[cur] = 1;
return 0;
}
pii nxt[MAXN];
pii prv[MAXN];
int pinch;
bool make_cyc(int s) {
vis[s] = 1;
for (pii e: edges[s]) {
if (dead[e.first]) continue;
if (vis[e.first]) {
nxt[s] = e;
pinch = e.first;
prv[e.first] = pii(s, e.second);
return 1;
}
if (make_cyc(e.first)) {
if (e.first != pinch && prv[nxt[e.first].first].first == e.first) prv[e.first] = pii(s, e.second);
nxt[s] = e;
return 1;
}
}
return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
n = N;
m = M;
for (int i = 0; i < m; i++) {
edges[U[i]].push_back(pii(V[i], i));
redges[V[i]].push_back(pii(U[i], i));
edge_list[i] = pii(U[i], V[i]);
indeg[V[i]]++;
outdeg[U[i]]++;
}
for (int i = 0; i < n; i++) {
if (!dead[i] && outdeg[i] == 0) prune(i);
}
if (dead[0]) return false;
par[0] = pii(-1, -1);
fill(par2, par2+n, pii(-1, -1));
if (!dfs(0)) return false;
return vector<int>({});
int t = 0;
while (t < path[0].size() && t < path[1].size() && path[0][t] == path[1][t]) {
t++;
}
assert(t < path[0].size() && t < path[1].size());
fill(nxt, nxt+n, pii(-1, -1));
fill(prv, prv+n, pii(-1, -1));
fill(vis, vis+n, 0);
bool b = make_cyc(cyc_node); assert(b); // goal is to evert the pinch cycle
vector<int> res;
for (int i = 0; i < t; i++) res.push_back(path[0][i]);
for (int _ = 0; _ < 2; _++) { // special case 0 is on cycle or smth
int j = t;
while (j < path[_].size() && nxt[edge_list[path[_][j]].first].first == -1) {
res.push_back(path[_][j]);
j++;
}
vector<int> to_rev;
int cur_node = (j == path[_].size() ? edge_list[path[_].back()].second : edge_list[path[_][j]].first);
while (prv[cur_node].first == -1) {
to_rev.push_back(nxt[cur_node].second);
res.push_back(nxt[cur_node].second);
cur_node = nxt[cur_node].first;
}
int cur = cur_node;
do {
if (_ == 0) {
res.push_back(nxt[cur].second);
cur = nxt[cur].first;
}
else {
res.push_back(prv[cur].second);
cur = prv[cur].first;
}
} while (cur != cur_node);
for (int i = to_rev.size()-1; i >= 0; i--) res.push_back(to_rev[i]);
for (int i = j-1; i >= t; i--) res.push_back(path[_][i]);
}
for (int i = t-1; i >= 0; t--) res.push_back(path[0][i]);
return res;
}
