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