#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)
v<int> anterior;
v<v<int>> adj;
v<int> vis;
v<int> cycle;
int beg;
void dfs(int n, int p=-1) {
if (beg != -1) return;
//cout << n << endl;
vis[n] = 1;
anterior[n] = p;
for (auto x : adj[n]) {
if (beg != -1) return;
//cout << x << " " << beg << " " << vis[x] << endl;
if (vis[x] == 1) {
cycle.clear();
int u = n;
beg = x;
while (anterior[u] != -1) {
cycle.push_back(u);
u = anterior[u];
}
cycle.push_back(u);
reverse(cycle.begin(), cycle.end());
return;
}
if (!vis[x]) {
dfs(x, n);
}
}
vis[n] == 2;
}
std::variant<bool, v<int>> find_journey(int N, int M, v<int> U, v<int> V) {
int n = N;
adj.resize(n);
anterior.resize(n);
vis.assign(n, 0);
beg = -1;
map<pii, v<int>> mp;
rep(i, 0, M) {
if (!mp.count({U[i], V[i]})) adj[U[i]].push_back(V[i]);
mp[{U[i], V[i]}].push_back(i);
}
dfs(0);
if (beg == -1) return false;
else {
v<int> ans;
int idx;
rep(i, 0, (int)cycle.size()) {
if (cycle[i] == beg) {
idx = i;
break;
}
ans.push_back(mp[{cycle[i], cycle[i+1]}][0]);
}
v<int> rev = ans;
reverse(rev.begin(), rev.end());
v<int> first;
rep(i, idx, (int)cycle.size()) {
int a, b;
a = cycle[i];
if (i == (int)cycle.size()-1) b = beg;
else b = cycle[i+1];
first.push_back(mp[{a, b}][0]);
}
for (auto x : first) ans.push_back(x);
reverse(first.begin(), first.end());
v<int> second;
rep(i, idx, (int)cycle.size()) {
int a, b;
a = cycle[i];
if (i == (int)cycle.size()-1) b = beg;
else b = cycle[i+1];
second.push_back(mp[{a, b}][1]);
}
for (auto x : second) ans.push_back(x);
reverse(second.begin(), second.end());
for (auto x : first) ans.push_back(x);
for (auto x : second) ans.push_back(x);
for (auto x : rev) ans.push_back(x);
return ans;
}
}
