#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
vector<vector<array<int, 2>>> adj(N);
vector<int> deg(N);
for (int i = 0; i < M; ++i) {
adj[U[i]].push_back({V[i], i});
}
vector<int> path;
vector<bool> vis(N);
int cycle_node = -1;
bool done = false;
vector<pair<int, int>> with_nodes;
auto dfs = [&](auto& dfs, int i, int lst) -> bool {
if (vis[i]) {
vector<pair<int, int>> to_cycle;
vector<int> rev;
while (with_nodes.back().second != i) {
to_cycle.push_back(with_nodes.back());
rev.push_back(with_nodes.back().first);
with_nodes.pop_back();
}
to_cycle.push_back(with_nodes.back());
rev.push_back(with_nodes.back().first);
with_nodes.pop_back();
reverse(begin(to_cycle), end(to_cycle));
// cout << "Found a cycle at " << i << ": ";
// for (auto& u : rev) {
// cout << u << " ";
// }
// cout << "\n";
int j = i;
int ptr = 0;
vector<int> nw;
do {
for (auto& [u, id] : adj[j]) {
// cout << to_cycle[ptr].first << " " << to_cycle[ptr].second << " , " << id << " " << u << "\n";
if (to_cycle[(ptr + 1) % (int)to_cycle.size()].second != u) continue;
if (to_cycle[ptr].first == id) continue;;
nw.push_back(id);
ptr += 1;
j = u;
break;
}
} while (j != i);
auto rev1 = nw;
reverse(begin(rev1), end(rev1));
path.insert(end(path), begin(nw), end(nw));
path.insert(end(path), begin(rev), end(rev));
path.insert(end(path), begin(rev1), end(rev1));
set<int> cycle;
for (auto& u : rev) cycle.insert(u);
for (auto& u : rev1) cycle.insert(u);
vector<int> rev2;
for (auto& u : path) {
if (cycle.count(u)) break;
rev2.push_back(u);
}
reverse(begin(rev2), end(rev2));
path.insert(end(path), begin(rev2), end(rev2));
// cout << "Appended cycle:\n";
// for (auto& u : path) {
// cout << u << " ";
// }
// cout << "\n";
return true;
}
vis[i] = 1;
for (auto& [u, id] : adj[i]) {
path.push_back(id);
with_nodes.push_back({id, i});
if (dfs(dfs, u, i)) {
return true;
}
path.pop_back();
with_nodes.pop_back();
}
vis[i] = 0;
return false;
};
if (dfs(dfs, 0, -1)) return path;
return false;
}
