#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#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 pll pair<lli,lli>
#define MAX 1000
//para el vector de hijos
#define des first
#define id second
vector<int> camino;
lli a,b,c,d,n;
lli vis[MAX+2];
stack<lli> ciclo;
vector<pll> hijos[MAX+2];
bool dfs(lli pos){
vis[pos] = 1;
lli cont = 0;
pll a = {-1,-1};
pll b = {-1,-1};
for(auto h : hijos[pos]) {
if(vis[h.des]) continue;
cont++;
if (a.des == -1) a = h;
else b = h;
}
if(cont == 0) return false;
else if(cont == 1) {
camino.push_back(a.id);
if(dfs(a.des)) {
camino.push_back(a.id);
return true;
}
else return false;
}
else {
lli w,x,y,z;
w = a.id;
x = (a.id^1);
y = b.id;
z = (b.id^1);
camino.push_back(w);
camino.push_back(x);
camino.push_back(y);
camino.push_back(z);
camino.push_back(x);
camino.push_back(w);
camino.push_back(z);
camino.push_back(y);
return true;
}
}
//solucion para la subtask #3
std::variant<bool, std::vector<int>> find_journey( int N, int M, std::vector<int> U, std::vector<int> V) {
n = N;
rep(i,0,M-1) {
if(i&1) continue;
hijos[U[i]].push_back({V[i],i});
hijos[V[i]].push_back({U[i],i+1});
}
if (dfs(0)) return camino;
else return false;
}
