#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
vector<pair<int, int>> adj[maxN];
int flag[maxN];
pair<int, int> par[maxN];
vector<int> cycle1;
vector<int> cycle2;
vector<int> suf;
void dfs(int u) {
if (!cycle1.empty()) {
return;
}
flag[u] = 2;
for (auto e: adj[u]) {
int v = e.first;
int id = e.second;
if (flag[v] == 2) {
cycle1.push_back(id);
cycle2.push_back(id ^ 1);
while (u != v) {
cycle1.push_back(par[u].second);
cycle2.push_back(par[u].second ^ 1);
u = par[u].first;
}
reverse(cycle1.begin(), cycle1.end());
reverse(cycle2.begin(), cycle2.end());
while (u != 0) {
suf.push_back(par[u].second);
u = par[u].first;
}
return;
}
if (flag[v] == 0) {
par[v] = {u, id};
dfs(v);
}
}
flag[u] = 1;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
if (N == 2) {
vector<int> left;
vector<int> right;
for (int i = 0; i < M; i++) {
if (U[i] == 0) {
left.push_back(i);
}
else {
right.push_back(i);
}
}
if ((int)left.size() < 2 || right.empty()) {
return false;
}
int A = left[0];
int B = right[0];
int C = left[1];
return vector<int>({A, B, C, A, B, C});
}
bool sub3 = (M % 2 == 0);
bool sub4 = (M % 2 == 0);
for (int i = 0; i < M; i += 2) {
sub3 &= (U[i] == V[i + 1] && V[i] == U[i + 1]);
sub4 &= (U[i] == U[i + 1] && V[i] == V[i + 1]);
}
if (sub3) {
for (int i = 0; i < M; i += 2) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i ^ 1);
}
if (adj[0].empty()) {
return false;
}
if ((int)adj[0].size() >= 2) {
int A = adj[0][0].second;
int B = A ^ 1;
int C = adj[0][1].second;
int D = C ^ 1;
return vector<int>({A, B, C, D, B, A, D, C});
}
int prv = 0;
int cur = adj[0][0].first;
vector<int> res = {adj[0][0].second};
while (true) {
if ((int)adj[cur].size() == 1) {
return false;
}
if ((int)adj[cur].size() >= 3) {
int A = -1;
int B = -1;
int C = -1;
int D = -1;
for (auto e: adj[cur]) {
int nxt = e.first;
int id = e.second;
if (nxt != prv) {
if (A == -1) {
A = id;
B = id ^ 1;
}
else if (C == -1) {
C = id;
D = id ^ 1;
}
}
}
vector<int> mid({A, B, C, D, B, A, D, C});
vector<int> suf(res.rbegin(), res.rend());
res.insert(res.end(), mid.begin(), mid.end());
res.insert(res.end(), suf.begin(), suf.end());
return res;
}
for (auto e: adj[cur]) {
int nxt = e.first;
int id = e.second;
if (nxt != prv) {
prv = cur;
cur = nxt;
res.push_back(id);
break;
}
}
}
return false;
}
if (sub4) {
for (int i = 0; i < M; i += 2) {
adj[U[i]].emplace_back(V[i], i);
}
dfs(0);
if (cycle1.empty()) {
return false;
}
vector<int> res(suf.rbegin(), suf.rend());
res.insert(res.end(), cycle1.begin(), cycle1.end());
res.insert(res.end(), cycle2.begin(), cycle2.end());
res.insert(res.end(), cycle1.rbegin(), cycle1.rend());
res.insert(res.end(), cycle2.rbegin(), cycle2.rend());
res.insert(res.end(), suf.begin(), suf.end());
return res;
}
int A = -1;
int B = -1;
int C = -1;
int D = -1;
for (int i = 0; i < M; i++) {
if (U[i] == 0 && V[i] == 1) {
A = i;
}
if (U[i] == 1 && V[i] == 0) {
B = i;
}
if (U[i] == 0 && V[i] == 2) {
C = i;
}
if (U[i] == 2 && V[i] == 0) {
D = i;
}
}
return vector<int>({A, B, C, D, B, A, D, C});
}
