#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll Nm = 1e5+5;
variant<bool,vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
if (N==2) {
vector<ll> vf,vr;
for (ll i=0;i<M;i++) {
if (U[i]==0) {
vf.push_back(i);
} else {
vr.push_back(i);
}
}
if (vf.size()<=1 || vr.size()<=0) {
return false;
} else {
return (vector<ll>) {vf[0],vr[0],vf[1],vf[0],vr[0],vf[1]};
}
}
map<pii,ll> mcnt; //map to count
map<pii,vector<ll>> mvec;
for (ll i=0;i<M;i++) {
if (mcnt.find({U[i],V[i]})==mcnt.end()) {
mcnt[{U[i],V[i]}]=0;
}
mcnt[{U[i],V[i]}]++;
mvec[{U[i],V[i]}].push_back(i);
}
bool f1 = 1, f2 = 1;
for (auto A0: mcnt) {
pii p0 = (A0).first;
if (mcnt[p0]%2!=0) {
f2 = 0;
}
if (mcnt[p0]!=mcnt[{p0.second,p0.first}]) {
f1 = 0;
}
}
if (f1) { //easier case
vector<array<ll,3>> adj[N];
for (auto A0: mcnt) {
pii p0 = A0.first;
if (p0.first>p0.second) {
continue;
}
vector<ll> v1 = mvec[p0];
vector<ll> v2 = mvec[{p0.second,p0.first}];
for (ll T=0;T<v1.size();T++) {
adj[p0.first].push_back({p0.second,v1[T],v2[T]});
adj[p0.second].push_back({p0.first,v1[T],v2[T]});
}
}
vector<ll> vcur;
if (adj[0].size()>=2) {
return (vector<ll>){adj[0][0][1],adj[0][0][2],adj[0][1][1],adj[0][1][2],adj[0][0][1],adj[0][0][2],adj[0][1][1],adj[0][1][2]};
} else if (adj[0].size()==0) {
return false;
}
ll xc = adj[0][0][0];
ll xp = 0;
while(1) {
if (adj[xc].size()>=3) {
ll i1,i2;
if (adj[xc][0][0]==xp) {
i1 = 1; i2 = 2;
} else if (adj[xc][1][0]==xp) {
i1 = 0; i2 = 2;
} else {
i1 = 0; i2 = 1;
}
vector<ll> vans = vcur;
vans.push_back(adj[xc][i1][1]);
vans.push_back(adj[xc][i1][2]);
vans.push_back(adj[xc][i2][1]);
vans.push_back(adj[xc][i2][2]);
vans.push_back(adj[xc][i1][1]);
vans.push_back(adj[xc][i1][2]);
vans.push_back(adj[xc][i2][1]);
vans.push_back(adj[xc][i2][2]);
for (ll T=(vcur.size()-1);T>=0;T--) {
vans.push_back(vcur[T]);
}
return vans;
} else if (adj[xc].size()==2) {
if (adj[xc][0][0]==xp) {
xp = xc; xc = adj[xc][1][0];
} else {
xp = xc; xc = adj[xc][0][0];
}
} else {
return false;
}
}
}
}
