#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 69;
int deg[N];
bool vis[N];
vector <pair<int, int>> adj[N];
vector <int> path, ok;
map <pair<int, int> , int> mp;
int n;
void dfs(int u){
vis[u] = true;
path.push_back(u);
if (deg[u] >= 3){
ok = path;
}
for (auto [v, i] : adj[u]){
if (!vis[v]) dfs(v);
}
path.pop_back();
}
void get(vector <int> &ans, int x, int y, int z){
ans.push_back(mp[{x, y}]);
ans.push_back(mp[{y, x}]);
ans.push_back(mp[{x, z}]);
ans.push_back(mp[{z, x}]);
ans.push_back(mp[{y, x}]);
ans.push_back(mp[{x, y}]);
ans.push_back(mp[{z, x}]);
ans.push_back(mp[{z, x}]);
}
variant<bool, vector<int>> find_journey(int nn, int m, vector<int> u, vector<int> v) {
n = nn;
for (int i = 0; i < m; i++){
adj[u[i]].push_back({v[i], i});
mp[{u[i], v[i]}] = i;
deg[u[i]]++;
}
vector <int> ans;
if (deg[0] >= 2){
int v1 = adj[0][0].first;
int v2 = adj[0][1].first;
get(ans, 0, v1, v2);
return ans;
} else {
return false;
}
dfs(0);
if (ok.size() == 0) return false;
vector <int> a1;
for (int i = 1; i < ok.size(); i++) a1.push_back(mp[{ok[i - 1], ok[i]}]);
ans = a1;
int v1, v2, v3, x, y;
x = ok.back();
y = ok[ok.size() - 2];
v1 = adj[x][0].first;
v2 = adj[x][1].first;
v3 = adj[x][2].first;
if (v1 != y && v2 != y)
get(ans, x, v1, v2);
else if (v1 == y) get(ans, x, v2, v3);
else get(ans, x, v1, v3);
reverse(a1.begin(), a1.end());
for (auto x : a1) ans.push_back(x);
return ans;
}
