#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
vector<int> AL[maxn];
deque<int> ans;
map<int,int> to[maxn];
map<int,int> to2[maxn];
bool dfs(int u,int p){
vector<int> good;
for(int v:AL[u]){
if(v==p)continue;
good.pb(v);
}
if(good.size()>=2){
int a,b,c,d;
if(good[0]==good[1])a=to[u][good[0]],b=to[good[0]][u],c=to2[u][good[1]],d=to2[good[1]][u];
else a=to[u][good[0]],b=to[good[0]][u],c=to[u][good[1]],d=to[good[1]][u];
ans.pb(a);ans.pb(b);ans.pb(c);ans.pb(d);
ans.pb(b);ans.pb(a);ans.pb(d);ans.pb(c);
return true;
}
for(int v:AL[u]){
if(v==p)continue;
if(dfs(v,u)){
ans.pf(to[u][v]),ans.pb(to[u][v]);
return true;
}
}
return false;
}
variant<bool,vector<int>> find_journey(int N,int M,vector<int> U,vector<int> V){
for(int i=0;i<M;++i){
AL[U[i]].pb(V[i]);
if(to[U[i]].find(V[i])!=to[U[i]].end())to2[U[i]][V[i]]=i;
else to[U[i]][V[i]]=i;
}
if(dfs(0,-1)){
vector<int> res;
for(int i:ans)res.pb(i);
return res;
}
return false;
}
