#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<multiset<pair<int, int>>> tadj(N);
vector<set<array<int, 3>>> adj(N);
vector<vector<pair<int, int>>> radj(N);
vector<int> ret, st;
for(int i=0; i<M; i++) tadj[U[i]].insert({V[i], i}), radj[V[i]].push_back({U[i], i});
queue<int> q;
auto del=[&]() {
while(!q.empty()) {
int curr=q.front(); q.pop();
for(auto [next, k]:radj[curr]) {
tadj[next].erase(tadj[next].find({curr, k}));
if(tadj[next].empty()) q.push(next);
}
radj[curr].clear();
}
};
int p=0;
for(int i=0; i<N; i++) if(tadj[i].empty()) q.push(i);
del();
if(tadj[0].empty()) return false;
while(tadj[p].size()==1) {
q.push(p), del();
if(tadj[p].empty()) return false;
st.push_back(tadj[p].begin()->second);
p=tadj[p].begin()->first;
}
for(int i=0; i<N; i++) if(!tadj[i].empty()) {
adj[i].insert({tadj[i].begin()->first, tadj[i].begin()->second, 0});
if(i==p) adj[i].insert({next(tadj[i].begin())->first, next(tadj[i].begin())->second, -1});
}
int curr=p, flag=0, t=0, prv=-1;
do {
bool flag2=false;
for(auto [next, k, f]:adj[curr]) if(!f && prv!=k) {
ret.push_back(k), flag+=1-2*f;
adj[next].insert({curr, k, 1-f}), adj[curr].erase({next, k, f});
curr=next, prv=k, flag2=true;
break;
}
if(flag2) continue;
for(auto [next, k, f]:adj[curr]) if(f && prv!=k) {
ret.push_back(k), flag+=1-2*f;
adj[next].insert({curr, k, 1-f}), adj[curr].erase({next, k, f});
curr=next, prv=k;
break;
}
} while(curr!=p || flag);
reverse(ret.begin(), ret.end());
reverse(st.begin(), st.end());
for(int i:st) ret.push_back(i);
reverse(ret.begin(), ret.end());
for(int i:st) ret.push_back(i);
return ret;
}
