#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,int>> adj[1005];
bool vis[1005];
bool test=false;
vector<int> ans;
bool dfs(int x,int p,int boat){
vis[x]=true;
if(boat!=-1) ans.push_back(boat);
if(adj[x].size()>=3){
int a=-1,b=-1,c=-1,d=-1;
for(auto u : adj[x]){
if(u.fi==p) continue;
if(a==-1) {
a=u.se;
for(auto i : adj[u.fi]) if(i.fi==x) c=i.se;
}
else if(b==-1) {
b=u.se;
for(auto i : adj[u.fi]) if(i.fi==x&&i.se!=c) d=i.se;
}
else break;
}
ans.push_back(a);
ans.push_back(c);
ans.push_back(b);
ans.push_back(d);
ans.push_back(c);
ans.push_back(a);
ans.push_back(d);
ans.push_back(b);
if(boat!=-1) ans.push_back(boat);
return true;
}
bool test=false;
for(auto u:adj[x]){
if(vis[u.fi]) continue;
if(dfs(u.fi,x,u.se)){
test=true;
break;
}
}
if(boat==-1) return test;
if(!test) ans.pop_back();
else ans.push_back(boat);
return test;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
for (int i = 0; i < M; ++i)
{
adj[U[i]].push_back({V[i],i});
}
if(adj[0].size()>=2){
int a = adj[0][0].se;
int b = adj[0][1].se;
int c;
int d;
for(auto u : adj[adj[0][0].fi]) if(u.fi==0) c=u.se;
for(auto u : adj[adj[0][1].fi]) if(u.fi==0&&u.se!=c) d=u.se;
return vector<int>({a,c,b,d,c,a,d,b});
}
if(dfs(0,-1,-1)) return ans;
return false;
}
