#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
vector<int> adj[N];
vector<int> cycle, path;
bool c[N], reach[N], vis[N];
int boat[N][N], bp, ava, n;
void dfs_sz(int v) {
reach[v] = 1;
for (auto& x : adj[v]) {
if (!reach[x]) dfs_sz(x);
}
}
bool dfs(int v, int p = -1) {
if (vis[v]) {
bp = v, ava = 1;
return true;
}
vis[v] = 1;
for (auto& x : adj[v]) {
if (x == p) continue;
if (dfs(x, v)) {
if (ava) cycle.push_back(v), c[v] = 1;
if (v == bp) ava = 0;
return true;
}
}
return false;
}
bool dfs2(int v, int p = -1) {
if (c[v]) {
path.push_back(v);
return true;
}
vis[v] = 1;
for (auto& x : adj[v]) {
if (!vis[x] && dfs2(x, v)) {
path.push_back(v);
return true;
}
}
return false;
}
variant<bool, vector<int>> find_journey(int _N, int M, vector<int> U, vector<int> V) {
n = _N;
bool ch = 0;
for (int i = 0;i < M;i++) {
adj[U[i]].push_back(V[i]);
}
dfs_sz(0);
memset(boat, -1, sizeof boat);
for (int i = 0;i < M;i++) {
if (!reach[U[i]]) continue;
if (boat[U[i]][V[i]] == -1) {
boat[U[i]][V[i]] = i;
}
else if (!ch) {
ch = 1;
cycle.push_back(U[i]), cycle.push_back(V[i]), c[U[i]] = c[V[i]] = 1;
}
}
if (!ch && !dfs(0)) return false;
// find path to cycle
memset(vis, 0, sizeof vis);
dfs2(0);
// path -> cycle -> elcyc -> htap
vector<int> ans;
{
int sz = path.size();
for (int i = 1;i < sz;i++) {
ans.push_back(boat[path[i - 1]][path[i]]);
}
}
{
vector<int> cycle2;
int last = path.back();
int sz = cycle.size();
for (int i = 0;i < sz;i++) {
if (cycle[i] == last) {
for (int j = 0;j < sz;j++) {
cycle2.push_back(cycle[(i + j) % sz]);
}
break;
}
}
cycle = cycle2;
}
int sz = cycle.size();
for (int i = 0;i < sz;i++) {
ans.push_back(boat[cycle[i]][cycle[(i + 1) % sz]]);
}
for (int i = sz - 1;i >= 0;i--) {
ans.push_back(boat[cycle[(i + 1) % sz]][cycle[i]]);
}
for (int i = sz - 1;i >= 0;i--) {
ans.push_back(boat[cycle[i]][cycle[(i + 1) % sz]]);
}
for (int i = 0;i < sz;i++) {
ans.push_back(boat[cycle[(i + 1) % sz]][cycle[i]]);
}
{
int sz = path.size();
for (int i = sz - 1;i >= 1;i--) {
ans.push_back(boat[path[i - 1]][path[i]]);
}
}
return ans;
}
