#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<vector<pair<int, int>>> adj(N), rev(N);
vector<int> out(N);
map<pair<int, int>, int> loc;
for (int i = 0; i < M; i++) {
adj[U[i]].emplace_back(V[i], i);
rev[V[i]].emplace_back(U[i], i);
out[U[i]]++;
loc[{U[i], V[i]}] = i;
}
// FIND ANY EDGE WITH DEGREE 2
int start = -1;
vector<int> ans;
if (out[0] >= 2) {
start = 0;
int left = adj[0][0].first;
int right = adj[0][1].first;
int a, b, c, d;
a = loc[{0, left}], b = loc[{left, 0}];
c = loc[{0, right}], d = loc[{right, 0}];
ans = {a, b, c, d, b, a, d, c};
return ans;
}
if (start == -1) {
vector<bool> vis(N);
vector<int> par(N, -1);
queue<int> q;
vis[0] = true;
q.emplace(0);
while (!q.empty()) {
auto u = q.front(); q.pop();
for (auto &[v, i] : adj[u]) {
if (!vis[v]) {
if (out[v] >= 3) {
start = v;
break;
}
par[v] = u;
vis[v] = true;
q.emplace(v);
}
}
}
int at = start;
vector<int> path;
while (at != -1) {
path.push_back(at);
at = par[at];
}
int m = path.size();
for (int i = m-1; i > 1; i--) {
int u = path[i], v = path[i-1];
ans.push_back(loc[{u, v}]);
}
vector<int> cands;
for (int i = 0; i < adj[start].size(); i++) {
if (adj[start][i].first == par[start]) continue;
cands.push_back(adj[start][i].first);
}
int left = cands[0], right = cands[1];
int a, b, c, d;
a = loc[{start, left}], b = loc[{left, start}];
c = loc[{start, right}], d = loc[{right, start}];
vector<int> temp = {a, b, c, d, b, a, d, c};
for (auto &x : temp) ans.push_back(x);
for (int i = 0; i < m-1; i++) {
int u = path[i], v = path[i+1];
ans.push_back(loc[{u, v}]);
}
return ans;
}
return false;
}
