#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define lli long long int
#define MAX 100000
#define des first
#define id second
int n,m;
vector<pair<int,int> > hijos[MAX];
vector<int> res;
bool solve(int pos,int padre) {
lli cont = 0;
pair<int,int> obj[2],regreso[2];
for (auto h : hijos[pos]){
if (h.des == padre) continue;
obj[cont] = h;
cont++;
if (cont == 2) break;
}
//tomar en cuenta que puede ser la misma balsa y estar usada
if (cont == 0) return false;
if (cont == 1) {
//caso en el cual sigues avanzando por ahi
res.push_back(obj[0].id);
if (solve(obj[0].des,pos)) {
res.push_back(obj[0].id);
return true;
}
else {
res.pop_back();
return false;
}
}
//caso en el que tu empiezas a ser true
for (auto h : hijos[obj[0].des]) {
if (h.des == pos) {
regreso[0] = {pos,h.id};
break;
}
}
for (auto h : hijos[obj[1].des]) {
if (h.des == pos && h != regreso[0]) {
regreso[1] = {pos,h.id};
break;
}
}
//pon la secuencia
int a = obj[0].id;
int b = regreso[0].id;
int c = obj[1].id;
int d = regreso[1].id;
res.push_back(a);
res.push_back(b);
res.push_back(c);
res.push_back(d);
res.push_back(b);
res.push_back(a);
res.push_back(d);
res.push_back(c);
return true;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
n = N;
m = M;
rep(i,0,m-1) hijos[U[i]].push_back({V[i],i});
if (solve(0,-1)) return res;
else return false;
}
