#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;
auto dfs = [&](auto& dfs, int i, int lst) -> bool {
int cnt = 0;
for (auto& [u, id] : adj[i]) {
if (u == lst) continue;
cnt += 1;
}
if (cnt >= 2) {
auto rev = path;
reverse(begin(rev), end(rev));
int c1 = -1, c2 = -1;
int u1 = -1, u2 = -1;
for (auto& [u, id] : adj[i]) {
if (u == lst) continue;
if (c1 == -1 || c2 == -1) {
if (u1 == -1) u1 = u;
else if (u1 != u) u2 = u;
if (c1 == -1) c1 = id;
else c2 = id;
}
}
assert(u1 != -1);
assert(c1 != -1);
assert(c2 != -1);
int c3 = -1, c4 = -1;
for (auto& [u, id] : adj[u1]) {
if (u == i) {
c3 = id;
break;
}
}
if (u2 != -1) {
for (auto& [u, id] : adj[u2]) {
if (u == i) {
c4 = id;
break;
}
}
}
assert(c3 != -1);
if (c4 == -1) {
path.push_back(c1);
path.push_back(c3);
path.push_back(c2);
path.push_back(c1);
path.push_back(c3);
path.push_back(c2);
} else {
path.push_back(c1);
path.push_back(c3);
path.push_back(c2);
path.push_back(c4);
path.push_back(c3);
path.push_back(c1);
path.push_back(c4);
path.push_back(c2);
}
path.insert(path.end(), begin(rev), end(rev));
return true;
}
for (auto& [u, id] : adj[i]) {
if (u == lst) continue;
path.push_back(id);
if (dfs(dfs, u, i)) {
return true;
}
path.pop_back();
}
return false;
};
if (dfs(dfs, 0, -1)) return path;
return false;
}
