#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int, int>> edge[1000];
int deg[1000];
int par[1000];
bool visited[1000];
void dfs(int v) {
visited[v] = true;
for (auto i : edge[v]) {
if (!visited[i.first]) {
par[i.first] = v;
dfs(i.first);
}
}
}
int f(int x) {
if (x & 1)
return x - 1;
return x + 1;
}
variant<bool, vector<int>> find_journey(int _n, int m, vector<int> u, vector<int> v) {
n = _n;
memset(par, -1, sizeof(par));
for (int i = 0; i < m; i++) {
edge[u[i]].push_back({ v[i],i });
deg[u[i]]++;
}
visited[0] = true;
dfs(0);
int x = -1;
for (int i = 0; i < n; i++) {
if (visited[i] && deg[i] > 2)
x = i;
}
if (deg[0] > 1)
x = 0;
if (x == -1)
return false;
vector<int> p;
for (int i = x;; i = par[i]) {
p.push_back(i);
if (!i)
break;
}
vector<int> ret;
for (int i = (int)p.size() - 1; i; i--) {
for (auto j : edge[p[i]]) {
if (j.first == p[i - 1]) {
ret.push_back(j.second);
break;
}
}
}
int sz = (int)ret.size();
pair<int, int> e1 = { -1,-1 }, e2 = { -1,-1 };
for (auto i : edge[x]) {
if (ret.empty() || ret[sz - 1] != f(i.second)) {
if (e1.second == -1)
e1 = { i.second,f(i.second) };
else if (e2.second == -1)
e2 = { i.second,f(i.second) };
}
}
ret.push_back(e1.first);
ret.push_back(e1.second);
ret.push_back(e2.first);
ret.push_back(e2.second);
ret.push_back(e1.second);
ret.push_back(e1.first);
ret.push_back(e2.second);
ret.push_back(e2.first);
for (int i = sz - 1; i >= 0; i--)
ret.push_back(ret[i]);
return ret;
}
