#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
bool dfs(ll n, ll edge_idx, vector<bool> &vis, vector<vector<ll>> &g, vector<ll> &u, vector<ll> &v, vector<ll> &opposite_edge, vector<ll> &journey){
vis[edge_idx] = 1;
vector<ll> x;
for(ll idx: g[n]) if(!vis[idx]) x.push_back(idx);
if(x.size() == 0) return 0;
if(x.size() == 1) {
journey.push_back(x[0]);
return dfs(v[x[0]], x[0], vis, g, u, v, opposite_edge, journey);
}
vector<ll> reversed_journey = journey;
reverse(reversed_journey.begin(), reversed_journey.end());
vector<ll> end_journey = {x[0], opposite_edge[x[0]], x[1], opposite_edge[x[1]], opposite_edge[x[0]], x[0], opposite_edge[x[1]], x[1]};
for(ll i: end_journey) journey.push_back(i);
for(ll i: reversed_journey) journey.push_back(i);
return 1;
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v) {
vector<vector<ll>> g(n);
vector<ll> opposite_edge(m);
vector<vector<ll>> edges(n, vector<ll>(n));
for(ll i = 0; i < m; i++) edges[u[i]][v[i]] = i;
for(ll i = 0; i < m; i++) {
g[u[i]].push_back(i);
opposite_edge[i] = edges[v[i]][u[i]];
}
vector<ll> journey;
vector<bool> vis(m+1);
if(!dfs(0, m, vis, g, u, v, opposite_edge, journey)) return false;
variant<bool, vector<int>> ans = (true, journey);
return ans;
}
