#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;
}
bool contains_cycle(ll n, ll p, vector<bool> &vis, vector<vector<ll>> &g, vector<ll> &u, vector<ll> &v){
vis[n] = 1;
for(ll idx: g[n]) {
if(vis[v[idx]]){
if(v[idx] != p) return 1;
}
else if(contains_cycle(v[idx], n, vis, g, u, v)) return 1;
}
return 0;
}
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);
for(ll i = 0; i < m; i++) {
g[u[i]].push_back(i);
if(i % 2 == 0) opposite_edge[i] = i+1;
else opposite_edge[i] = i-1;
}
vector<ll> journey;
vector<bool> vis(m+1), cycle_test_vis(n);
if(!dfs(0, m, vis, g, u, v, opposite_edge, journey) && !contains_cycle(0, -1, cycle_test_vis, g, u, v)) return false;
variant<bool, vector<int>> ans = (true, journey);
return ans;
}
