#include "islands.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <variant>
#include <map>
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), ins(n);
vector<int> estk, vstk, ans;
auto dfs = [&] (auto dfs, int u, int frm) -> bool {
vstk.push_back(u);
ins[u] = true;
vis[u] = true;
for (auto [v, id]: adj[u]) {
if (vis[v]) {
if (!ins[v]) continue;
vector<int> cyc;
cyc.push_back(id);
while (vstk.back() != v) {
cyc.push_back(estk.back());
estk.pop_back();
vstk.pop_back();
}
reverse(cyc.begin(), cyc.end());
ans.clear();
ans.insert(ans.end(), estk.begin(), estk.end());
ans.insert(ans.end(), cyc.begin(), cyc.end());
for (int &x: cyc) x ^= 1;
ans.insert(ans.end(), cyc.begin(), cyc.end());
for (int &x: cyc) x ^= 1;
ans.insert(ans.end(), cyc.rbegin(), cyc.rend());
for (int &x: cyc) x ^= 1;
ans.insert(ans.end(), cyc.rbegin(), cyc.rend());
for (int &x: cyc) x ^= 1;
ans.insert(ans.end(), estk.rbegin(), estk.rend());
return true;
}
estk.push_back(id);
if (dfs(dfs, v, id)) return true;
estk.pop_back();
}
vstk.pop_back();
ins[u] = false;
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+=2) g.add_edge(U[i], V[i], i);
auto ans = g.solve();
if (ans.size()) return true, ans;
return false;
}
