#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#define fs first
#define sc second
using namespace std;
vector<int> dep,fa;
vector<vector<pair<int,int> > > e;
void dfs(int r,int f){
dep[r]=dep[f]+1;
fa[r]=f;
for(auto h:e[r]){
if(dep[h.fs]<0){
dfs(h.fs,r);
}
}
}
vector<int> dg[2];
vector<int> ss;
int dfs3(int r,int g,int k){
for(auto h:e[r]){
if(!ss[h.sc]){
ss[h.sc]=1;
dg[k].push_back(h.sc);
if(h.fs==g){
return 1;
}
if(dfs3(h.fs,g,k)){
return 1;
}
ss[h.sc]=0;
dg[k].pop_back();
}
}
return 0;
}
int dfs2(int r){
int a=dfs3(r,r,0);
if(a){
int b=dfs3(r,r,1);
if(!b){
for(auto h:dg[0]){
ss[h]=0;
}
dg[0].clear();
}
return b;
}
return 0;
}
variant<bool, vector<int>> find_journey(
int n, int m, vector<int> u, vector<int> v) {
e.resize(n);
ss.resize(m);
fa.resize(n);
dep.resize(n,-1);
for(int i=0;i<m;i++){
e[u[i]].push_back({v[i],i});
}
dfs(0,0);
for(int i=0;i<n;i++){
if(dep[i]>=0){
if(dfs2(i)){
vector<int> az,bz;
for(int j=i;j!=0;j=fa[j]){
az.push_back(j);
}
for(int j=0;j!=i;){
for(auto h:e[j]){
if(h.fs==az.back()){
az.pop_back();
bz.push_back(h.sc);
j=h.fs;
break;
}
}
}
vector<int> ans;
ans.insert(ans.end(),bz.begin(),bz.end());
ans.insert(ans.end(),dg[0].begin(),dg[0].end());
ans.insert(ans.end(),dg[1].begin(),dg[1].end());
reverse(dg[0].begin(),dg[0].end());
reverse(dg[1].begin(),dg[1].end());
ans.insert(ans.end(),dg[0].begin(),dg[0].end());
ans.insert(ans.end(),dg[1].begin(),dg[1].end());
reverse(bz.begin(),bz.end());
ans.insert(ans.end(),bz.begin(),bz.end());
return ans;
}
}
}
return false;
}
