#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
vector<pair<int,int>>g[N];
bool used[N];
deque<int>path;
int inv(int x){
if(x%2==0){
return x+1;
}
return x-1;
}
bool dfs(int v){
if(used[v])return false;
used[v]=true;
if(g[v].size()>=3){
if(used[g[v][0].ff])swap(g[v][0],g[v][1]);
if(used[g[v][1].ff])swap(g[v][1],g[v][2]);
path.push_back(g[v][0].ss);
path.push_back(inv(g[v][0].ss));
path.push_back(g[v][1].ss);
path.push_back(inv(g[v][1].ss));
path.push_back(inv(g[v][0].ss));
path.push_back(g[v][0].ss);
path.push_back(inv(g[v][1].ss));
path.push_back(g[v][1].ss);
return true;
}
for(pair<int,int> to:g[v]){
if(dfs(to.ff)){
path.push_front(to.ss);
path.push_back(to.ss);
return true;
}
}
return false;
}
variant<bool, vector<int>> find_journey(int NN, int MM, vector<int> U, vector<int> V) {
n=NN;
m=MM;
for(int i=0;i<m;i++){
g[U[i]].push_back({V[i],i});
}
if(g[0].size()>=2){
vector<int>ans = {g[0][0].ss,inv(g[0][0].ss),
g[0][1].ss,inv(g[0][1].ss),
inv(g[0][0].ss),g[0][0].ss,
inv(g[0][1].ss),g[0][1].ss};
return ans;
}
if(dfs(0)){
vector<int>ans;
for(int x:path)ans.push_back(x);
return ans;
}
return false;
}
