#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<vector<pair<int, int>>> G(N);
for (int i = 0; i < M; i++) {
G[U[i]].emplace_back(V[i], i);
}
vector<int> B(N, -1), ans;
function<bool(int)> dfs = [&](int A) {
if (A == 0) {
if (G[0].size() > 1) {
int X = G[0][0].second;
int Y = X ^ 1;
int Z = G[0][1].second;
int T = Z ^ 1;
ans = vector<int>({X, Y, Z, T, Y, X, T, Z});
return true;
} else if (G[0].size() == 1) {
auto [E, F] = G[0][0];
B[E] = F;
if (dfs(E)) {
return true;
}
}
} else {
if (G[A].size() > 2) {
vector<int> a;
int C = A;
while (C != 0) {
a.push_back(B[C]);
C = U[B[C]];
}
int X = (B[A] == (G[A][0].second ^ 1)) ? G[A][1].second : G[A][0].second;
int Y = X ^ 1;
int Z = (B[A] == (G[A][2].second ^ 1)) ? G[A][1].second : G[A][2].second;
int T = Z ^ 1;
for (int i = a.size() - 1; i >= 0; i--) {
ans.push_back(a[i]);
}
for (int C : vector<int>({X, Y, Z, T, Y, X, T, Z})) {
ans.push_back(C);
}
for (int i = 0; i < a.size(); i++) {
ans.push_back(a[i]);
}
return true;
} else if (G[A].size() == 2) {
pair<int, int> P;
if (B[A] == (G[A][0].second ^ 1)) {
P = G[A][1];
} else {
P = G[A][0];
}
auto [E, F] = P;
if (B[E] == -1) {
B[E] = F;
if (dfs(E)) {
return true;
}
}
}
}
return false;
};
B[0] = -2;
if (dfs(0)) {
return ans;
} else {
return false;
}
}
