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