#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
#define var variant
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 1e5 + 5;
int n, m;
arr<vec<pii>, N> adj;
vec<int> ans;
arr<bool, N> vs;
bool dfs(int u = 1) {
vs[u] = true;
vec<pii> ngh;
for (auto [v, i] : adj[u])
if (!vs[v]) ngh.push_back({v, i});
if (ngh.size() <= 1) {
for (auto [v, i] : ngh) {
ans.push_back(i);
if (dfs(v)) return true;
}
return false;
}
int a = ngh[0].sec, b = (a % 2 == 0) ? a + 1 : a - 1;
int c = ngh[1].sec, d = (c % 2 == 0) ? c + 1 : c - 1;
vec<int> x = ans;
vec<int> y = {a, b, c, d, b, a, d, c};
vec<int> z = ans;
reverse(z.begin(), z.end());
ans.clear();
for (vec<int> w : {x, y, z})
ans.insert(ans.end(), w.begin(), w.end());
return true;
}
var<bool, vec<int>> find_journey(int _n, int _m, vec<int> _u, vec<int> _v) {
n = _n, m = _m;
for (int i = 0; i < m; i++) {
int u = _u[i] + 1, v = _v[i] + 1;
adj[u].push_back({v, i});
}
if (!dfs()) return false;
return ans;
}
