#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector <int> v[200001];
int vis[200001];
map <array<int,2>,int> mp;
vector <int> cycle,path;
int solve(int i,int last){
vis[i]=1;
for(int j:v[i]){
if(last!=j&&vis[j]==1){
cycle.push_back(i);
return j;
}
if(vis[j]==0){
int val=solve(j,i);
if(val>=0){
cycle.push_back(i);
if(val==i) return -2;
else return val;
}
else if(val==-2){
path.push_back(i);
return -2;
}
}
}
return -1;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
n=N,m=M;
for(int i=0;i<m;i++){
v[U[i]].push_back(V[i]);
mp[{U[i],V[i]}]=i;
}
solve(0,-1);
if(cycle.size()==0) return false;
reverse(path.begin(),path.end());
reverse(cycle.begin(),cycle.end());
// cout<<"PATH"<<" ";
// for(int i:path) cout<<i<<" ";
// cout<<endl;
// cout<<"CYCLE"<<" ";
// for(int i:cycle) cout<<i<<" ";
// cout<<endl;
vector <int> ans;
for(int i=0;i<path.size()-1;i++){
ans.push_back(mp[{path[i],path[i+1]}]);
}
ans.push_back(mp[{path.back(),cycle[0]}]);
ans.push_back(mp[{cycle[0],cycle.back()}]);
ans.push_back(mp[{cycle.back(),cycle[0]}]);
for(int i=0;i<cycle.size()-1;i++){
ans.push_back(mp[{cycle[i],cycle[i+1]}]);
}
ans.push_back(mp[{cycle[0],cycle.back()}]);
ans.push_back(mp[{cycle.back(),cycle[0]}]);
for(int i=cycle.size()-1;i>=1;i--){
ans.push_back(mp[{cycle[i-1],cycle[i]}]);
}
for(int i=path.size()-1;i>0;i--){
ans.push_back(mp[{path[i-1],path[i]}]);
}
return ans;
}
// 6 12
// 0 3
// 3 0
// 3 2
// 2 3
// 1 2
// 2 1
// 1 4
// 4 1
// 5 4
// 4 5
// 2 5
// 5 2
