#include "islands.h"
#include "bits/stdc++.h"
using namespace std;
#define ii pair<int,int>
const int MAX_N=1e5+5;
int piv=-1;
vector<int> path,res;
vector<pair<int,ii>> adj[MAX_N];
vector<bool> vis(MAX_N,false);
void dfs(int u, int pa){
if(piv!=-1) return;
vis[u]=true;
if((!u && adj[u].size()>=2) || (u && adj[u].size()>=3)){
piv=u;
int a=-1,b=-1,c=-1,d=-1;
for(auto v: adj[u]){
if(v.first==pa) continue;
if(a==-1)
a=v.second.first,b=v.second.second;
else{
c=v.second.first,d=v.second.second;
break;
}
}
res=path;
for(int i: {a,b,c,d,b,a,d,c}) res.push_back(i);
for(int i=path.size()-1;i>=0;i--) res.push_back(path[i]);
return;
}
for(auto v: adj[u]){
if(vis[v.first]) continue;
path.push_back(v.second.first);
dfs(v.first,u);
path.pop_back();
}
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v){
for(int i=0;i<m;i+=2){
adj[u[i]].push_back({v[i],{i,i+1}});
adj[v[i]].push_back({u[i],{i+1,i}});
}
dfs(0,-1);
if(piv==-1) return false;
return res;
}
