#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() {
if (adj[0].size() == 0) return {};
if (adj[0].size() >= 2) {
auto [v, x] = adj[0][0];
auto [w, y] = adj[0][1];
return {x, x^1, y, y^1, x^1, x, y^1, y};
}else{
auto [v, x] = adj[0][0];
int i = -1;
for (auto [w, id]: adj[v]) if (id != (x^1)) i = id;
if (i == -1) return {};
int j = x^1;
int k = i^1;
return {x, i, k, j, i, k, j, x};
}
}
};
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;
}
