#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
vector<int> adj[maxN];
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];
vector<int> res = {A, B, C, A, B, C};
return res;
}
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]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
if (adj[0].empty()) {
return false;
}
if ((int)adj[0].size() >= 2) {
return true;
}
int prv = 0;
int cur = adj[0][0];
while (true) {
if ((int)adj[cur].size() == 1) {
return false;
}
if ((int)adj[cur].size() >= 3) {
return true;
}
int nxt = adj[cur][0] == prv ? adj[cur][1] : adj[cur][0];
prv = cur;
cur = nxt;
}
return false;
}
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;
}
}
vector<int> res = {A, B, C, D, B, A, D, C};
return res;
}
