#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
bool find_split(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 find_split(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 not_line(ll n, ll p, vector<bool> &vis, vector<vector<ll>> &g, vector<ll> &u, vector<ll> &v){
vis[n] = 1;
ll cnt = 0;
for(ll idx: g[n]) {
if(vis[v[idx]]){
if(v[idx] != p) return 1;
}
else {
cnt++;
if(not_line(v[idx], n, vis, g, u, v)) return 1;
}
}
return cnt > 1;
}
void solve_cyc(ll n, ll p, vector<bool> &vis, vector<vector<ll>> &g, vector<ll> &u, vector<ll> &v, vector<ll> &opposite_edge, vector<ll> &route, vector<ll> &journey, vector<vector<ll>> &edges){
vis[n] = 1;
ll cnt = 0;
for(ll idx: g[n]) {
if(vis[v[idx]]){
if(v[idx] != p) {
vector<ll> journey_before_cyc = journey;
journey.push_back(idx);
journey.push_back(opposite_edge[idx]);
ll prev = v[idx];
while(route.back() != v[idx]) journey.push_back(edges[route.back()][prev]), journey_before_cyc.pop_back(), prev = route.back(), route.pop_back();
journey.push_back(opposite_edge[idx]);
journey.push_back(idx);
while(journey_before_cyc.size()) journey.push_back(journey_before_cyc.back()), journey_before_cyc.pop_back();
}
}
else {
journey.push_back(idx);
route.push_back(v[idx]);
solve_cyc(v[idx], n, vis, g, u, v, opposite_edge, route, journey, edges);
}
}
}
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> split_journey, cyc_journey, route;
vector<bool> split_vis(m+1), cyc_vis(m+1), line_test_vis(n);
if(!not_line(0, -1, line_test_vis, g, u, v)) return false;
if(find_split(0, m, split_vis, g, u, v, opposite_edge, split_journey)) return (true, split_journey);
vector<vector<ll>> edges(n, vector<ll>(n));
for(ll i = 0; i < m; i++) edges[u[i]][v[i]] = i;
solve_cyc(0, -1, cyc_vis, g, u, v, opposite_edge, route, cyc_journey, edges);
return (true, cyc_journey);
}
