#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define ln '\n';
template <class F, class S>
bool chmin(F &u, const S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
int n = N, m = M;
// subtask #4
vector <vector<int>> adj(n);
map <pair<int,int>,vector<int>> id;
for ( int i = 0; i < m; i += 2 ){
adj[U[i]].pb(V[i]);
id[{U[i], V[i]}].pb(i);
}
vector <int> us(n), path, a;
int sx = -1;
auto dfs = [&](auto dfs, int u) -> void{
if ( sx != -1 ) return;
path.pb(u);
us[u] = 1;
for ( auto &v: adj[u] ){
if ( sx != -1 ) return;
if ( !us[v] ){
dfs(dfs, v);
} else if ( us[v] == 1 ){ // cycle found
sx = v; a = path;
return;
}
}
path.pop_back();
us[u] = 2;
};
dfs(dfs, 0);
if ( sx == -1 ){
return false;
}
vector <int> ans;
int s = a.size(), j = -1;
for ( int i = 0; i < s; i++ ){
if ( a[i] == sx ){
j = i; break;
}
assert(i + 1 < s);
ans.pb(id[{a[i], a[i + 1]}][0]);
}
vector <int> tmp;
for ( int i = j; i < s; i++ ){
int nxt = (i + 1 < s ? i + 1 : j);
ans.pb(id[{a[i], a[nxt]}][0]);
}
for ( int i = j; i < s; i++ ){
int nxt = (i + 1 < s ? i + 1 : j);
ans.pb(id[{a[i], a[nxt]}][1]);
}
for ( int i = s - 1; i >= j; i-- ){
int nxt = (i + 1 < s ? i + 1 : j);
ans.pb(id[{a[i], a[nxt]}][0]);
}
for ( int i = s - 1; i >= j; i-- ){
int nxt = (i + 1 < s ? i + 1 : j);
ans.pb(id[{a[i], a[nxt]}][1]);
}
for ( int i = j - 1; i >= 0; i-- ){
ans.pb(id[{a[i], a[i + 1]}][0]);
}
return ans;
}
