#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
vi InDeg(n, 0), OutDeg(n, 0);
vector<vector<ii> > L(n);
map<ii, int> Id, Per2;
map<int, int> Per;
for(int i = 0; i < m; ++i) {
L[U[i]].push_back({V[i], i});
Id[{U[i], V[i]}] = i;
Per2[{V[i], U[i]}] = i;
++OutDeg[U[i]];
++InDeg[V[i]];
}
for(int i = 0; i < m; ++i) {
Per[i] = i ^ 1;
if(m == n * (n - 1))
Per[i] = Per2[{U[i], V[i]}];
}
bool ok = false;
vi viz(n, 0);
stack<ii> S;
vi Re;
function<void(int, int, int)> dfs = [&](int u, int p, int parc) {
if(ok) return;
if(viz[u] == 2) return;
if(viz[u] == 1) {
return;
vector<ii> Cic;
while(!S.empty() && S.top().first!= u) {
Cic.push_back(S.top());
S.pop();
}
// if(!S.empty())
// S.pop(); /// ????
reverse(Cic.begin(), Cic.end());
Cic.push_back({u, parc});
vector<ii> Rest;
while(!S.empty()) {
Rest.push_back(S.top());
S.pop();
}
vi Sol;
for(auto it : Rest)
Sol.push_back(it.second);
for(auto it : Cic)
Sol.push_back(it.second);
reverse(Cic.begin(), Cic.end());
for(auto it : Cic)
Sol.push_back(it.second ^ 1);
reverse(Cic.begin(), Cic.end());
for(auto it : Cic)
Sol.push_back(it.second);
reverse(Cic.begin(), Cic.end());
for(auto it : Cic)
Sol.push_back(it.second ^ 1);
reverse(Rest.begin(), Rest.end());
for(auto it : Rest)
Sol.push_back(it.second);
Re = Sol;
ok = 1;
return;
}
if(parc != -1)
S.push({u, parc});
viz[u] = 1;
int nrf = 0;
vector<ii> Fii;
for(auto [it, nrc] : L[u]) {
if(it != p) {
++nrf;
Fii.push_back({it, nrc});
}
}
if(nrf > 1) {
vector<ii> SV;
while(!S.empty()) {
SV.push_back(S.top());
S.pop();
}
reverse(SV.begin(), SV.end());
vi Sol;
for(auto [a, b] : SV)
Sol.push_back(b);
int f0 = Fii[0].second, f1 = Fii[1].second;
Sol.push_back(f0);
Sol.push_back(Per[f0]);
Sol.push_back(f1);
Sol.push_back(Per[f1]);
Sol.push_back(Per[f0]);
Sol.push_back(f0);
Sol.push_back(Per[f1]);
Sol.push_back(f1);
reverse(SV.begin(), SV.end());
for(auto [a, b] : SV)
Sol.push_back(b);
ok = true;
Re = Sol;
}
for(auto [it, nrc] : L[u]) {
if(it != p) {
dfs(it, u, nrc);
}
}
viz[u] = 2;
};
dfs(0, -1, -1);
if(ok && !Re.empty()) return Re;
return ok;
}
