#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define f0(i, n) for(int i = 0; i < (n); i++)
#define f1(i, n) for(int i = 1; i <= (n); i++)
#define ff first
#define ss second
#define pb push_back
int opp(int n) {
if(n % 2 == 0) return n+1;
return n-1;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
if(N == 2) {
vi zr, on;
f0(i, M) {
if(U[i] == 0) zr.pb(i);
else on.pb(i);
}
if(zr.size() < 2 || on.size() < 1) return false;
return vi({zr[0], on[0], zr[1], zr[0], on[0], zr[1]});
}
bool sbtsk3 = (M % 2 == 0);
bool sbtsk4 = (M % 2 == 0);
f0(i, M - 1) {
if(i % 2 == 0) {
if(U[i] != V[i+1] || V[i] != U[i+1]) {
sbtsk3 = false;
}
if(U[i] != U[i+1] || V[i] != V[i+1]) {
sbtsk4 = false;
}
}
}
if(sbtsk3) {
vector<pair<int, int>> grph[N];
bool vis[N] = {0};
f0(i, M) {
grph[U[i]].pb({V[i], i});
}
vi ans, t_ans;
int cur = 0;
vis[cur] = true;
if(grph[cur].size() > 1) {
int x = grph[cur][0].ss, y = grph[cur][1].ss;
return vi({x, opp(x), y, opp(y), opp(x), x, opp(y), y});
} else {
ans.pb(grph[cur][0].ss);
cur = grph[cur][0].ff;
}
vis[cur] = true;
while(grph[cur].size() <= 2) {
if(grph[cur].size() == 1) return false;
for(auto nxt: grph[cur]) {
if(!vis[nxt.ff]) {
ans.pb(nxt.ss);
cur = nxt.ff;
vis[cur] = true;
}
}
}
for(auto nxt: grph[cur]) {
if(!vis[nxt.ff]) {
t_ans.pb(nxt.ss);
}
}
int x = t_ans[0], y = t_ans[1];
t_ans.clear();
t_ans = vi(ans.rbegin(), ans.rend());
ans.pb(x);
ans.pb(opp(x));
ans.pb(y);
ans.pb(opp(y));
ans.pb(opp(x));
ans.pb(x);
ans.pb(opp(y));
ans.pb(y);
for(int e: t_ans) ans.pb(e);
return ans;
}
if (N == 4) {
return std::vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
}
return false;
}
