#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
int n, m;
vector<vi> adj;
vi istate;
variant<bool, vi> find_journey(int N, int M, vi U, vi V) {
n = N; m = M; istate.assign(n, 0); adj.resize(n);
map<pi, int> ec;
for (int i = 0; i < m; i++) {
ec[{U[i], V[i]}]++;
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
}
auto find = [&](int u, int v, int skip = -1) {
for (int i = 0; i < m; i++) {
if (U[i] == u && V[i] == v && i != skip) return i;
}
return -1;
};
auto get_case1 = [&](int u, int p) {
for (auto e : adj[u]) {
int v = U[e] == u ? V[e] : U[e];
if (v == p) continue;
if (ec[{u, v}] >= 2 && ec[{v, u}] >= 1) {
int a = find(u, v), c = find(v, u); int b = find(u, v, a);
return vector<int>({a, c, b, a, c, b});
}
}
return vector<int>({});
};
if (n == 2) {
auto c1 = get_case1(0, -1);
if (c1.empty()) return false;
else return c1;
}
vector<int> pre, maneuver, post;
set<int> vis;
auto dfs_c1 = [&](auto &&self, int u, int p) {
auto c1 = get_case1(u, p);
if (!c1.empty()) {
maneuver = c1;
return true;
}
vis.insert(u);
for (auto e : adj[u]) {
int v = U[e] == u ? V[e] : U[e];
if (v == p) continue;
if (vis.count(v)) continue;
if (self(self, v, u)) {
post.push_back(e);
return true;
}
}
return false;
};
if (dfs_c1(dfs_c1, 0, -1)) {
pre = post;
reverse(pre.begin(), pre.end());
for (auto &el : maneuver) pre.push_back(el);
for (auto &el : post) pre.push_back(el);
return pre;
}
int timer = 0;
vis.clear(); vi tin(n+1, -1);
auto dfs_c2 = [&](auto &&self, int u, int p) {
vis.insert(u);
tin[u] = timer++;
for (auto e : adj[u]) {
int v = U[e] == u ? V[e] : U[e];
if (v == p) {
if (ec[{u, v}] >= 2 && ec[{v, u}] >= 2) return true;
else continue;
}
if (!(ec[{u, v}] > 0 && ec[{v, u}] > 0)) continue;
if (vis.count(v)) {
if (tin[v] < tin[u]) return true;
else continue;
}
if (self(self, v, u)) {
return true;
}
}
return false;
};
if (dfs_c2(dfs_c2, 1, -1)) return true;
// int a = find(0, 1), b = find(1, 0), c = find(1, 2), d = find(2, 1), e = find(2, 0), f = find(0, 2);
// return vector<int>({a, c, e, f, d, b, e, c, a, b, d, f});
return false;
}
