#include "islands.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <variant>
using namespace std;
struct Graph {
int n;
vector<vector<pair<int, int>>> adj;
Graph(int _n) : n(_n), adj(n) {}
void add_edge(int u, int v, int id) {
adj[u].push_back({v, id});
}
vector<int> solve() {
vector<bool> vis(n);
vector<int> stk, ans;
auto dfs = [&] (auto dfs, int u, int frm) -> bool {
vis[u] = true;
vector<int> ls;
for (auto [v, id]: adj[u]) {
if (id != (frm ^ 1)) ls.push_back(id);
}
if (ls.size() >= 2) {
int x = ls[0], y = ls[1];
ans.clear();
ans.insert(ans.end(), stk.begin(), stk.end());
ans.push_back(x);
ans.push_back(x^1);
ans.push_back(y);
ans.push_back(y^1);
ans.push_back(x^1);
ans.push_back(x);
ans.push_back(y^1);
ans.push_back(y);
ans.insert(ans.end(), stk.rbegin(), stk.rend());
return true;
}
for (auto [v, id]: adj[u]) {
if (vis[v]) continue;
stk.push_back(id);
if (dfs(dfs, v, id)) return true;
stk.pop_back();
}
return false;
};
dfs(dfs, 0, -1);
return ans;
}
};
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V)
{
int n = N, m = M;
if (n == 2) {
vector<int> c[2];
for (int i=0; i<M; i++) c[U[i]].push_back(i);
if (c[0].size() < 2 || c[1].size() < 1) return false;
int x = c[0][0], y = c[0][1];
int z = c[1][0];
vector<int> ans = {x, z, y, x, z, y};
return true, ans;
}
Graph g(n);
for (int i=0; i<m; i++) g.add_edge(U[i], V[i], i);
auto ans = g.solve();
if (ans.size()) return true, ans;
return false;
}
